Vikipedio:Projekto matematiko/Ajgena algoritmo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Ajgena algoritmo
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En lineara algebro, unu de la plej grava (problemoj, problemas) estas (dezajnanta, dizajnanta, projektanta, desegnanta) kompetenta kaj stabila (algoritmoj, algoritmas) por trovanta la (ajgenoj, ajgenas) de matrico. Ĉi tiuj ajgenaj algoritmoj (majo, povas) ankaŭ trovi (ajgenvektoroj, ajgenvektoras).

[redaktu] Karakteriza polinomo

Donita matrico A, ajgeno λ kaj ĝia asociita ajgenvektoro v estas, per difino, paro tia (tiu, ke, kiu)

$A{\bold v} = \lambda{\bold v} \,\! .$

Ekvivalente, (A−λMi)v = 0, (implicanta, enhavanta) _det_(A−λMi) = 0. Ĉi tiu determinanto elvolvas al polinomo en λ, (nomita, vokis) la karakteriza polinomo de A. Unu komuna maniero por trovanta la (ajgenoj, ajgenas) de malgranda matrico estas per trovanta (radikoj, radikas) de la karakteriza polinomo. Ĉi tiu estas eksplikita en pli detalo en la artikola Signa kalkulado de matricaj ajgenoj.

Bedaŭrinde, ĉi tiu maniero havas iuj limigoj. Ĝenerala polinomo de (mendi, ordo) n > 4 ne povas esti solvita per (finia vico, finilonga vico) de aritmetikaj operacioj kaj radikaloj (vidi Abelo-_Ruffini_ teoremo). Tie fari ekzisti kompetentaj radiko-trovantaj algoritmoj por pli alta (mendi, ordo) (polinomoj, polinomas). Tamen, trovanta la (radikoj, radikas) de la karakteriza polinomo (majo, povas) esti miskondiĉa problemo (eĉ, ebena, para) kiam la suba ajgena problemo estas bonkondiĉa. Por ĉi tiu kaŭzo, ĉi tiu maniero estas malofte uzita.

La pli supre diskuto (implicas, enhavas) limigo sur ĉiuj ajgenaj algoritmoj. Ĝi povas esti montrita (tiu, ke, kiu) por (ĉiu, iu) polinomo, tie ekzistas matrico (vidi kompaniula matrico) havanta (tiu, ke, kiu) polinomo kiel ĝia karakteriza polinomo (reale, estas malfinie multaj). Se tie farita ekzisti (finia vico, finilonga vico) de aritmetikaj operacioj por akurate trovanta la (ajgenoj, ajgenas) de ĝenerala matrico, ĉi tiu devus provizi (korespondanta, respektiva) (finia vico, finilonga vico) por ĝenerala (polinomoj, polinomas), en kontraŭdiro de la Abelo-_Ruffini_ teoremo. Pro tio, ĝeneralaj ajgenaj algoritmoj estas atendita al esti ripeta.

[redaktu] Pova ripeto

La baza ideo de ĉi tiu maniero estas al elekti komenca vektoro b (ĉu ajgenvektora proksimuma kalkulado aŭ hazarda vektoro) kaj tiam multfoje multipliki ĝi per la matrico, ripete kalkulanta Ab, A²b, A³b,…. Supozi la (ajgenoj, ajgenas) estas (mendita, ordita) per grandeco, kun λ₁ estante la plej granda, kaj kun asociita ajgenvektoro v₁. Tiam ĉiu ripeto (krustoj, krustas, skaloj, skalas) la komponanto de b en la v₁ direkto per λ₁, kaj ĉiu alia direkto per (pli minuskla, pli malgranda) kvanto (alprenanta |λ₂| < |λ₁|). Krom aro de mezura nulo, por (ĉiu, iu) komenca vektoro la rezulto estos konverĝi al ajgenvektoro (korespondanta, respektiva) al la domina ajgeno. En praktiko, la vektoro devus esti ununormigita post ĉiu ripeto.

Per sin, pova ripeto estas ne tre utila. Ĝia konverĝo estas malfrua krom specialaj okazoj de matricoj, kaj sen ŝanĝo, ĝi povas nur trovi la plej granda aŭ domina ajgeno (kaj la (korespondanta, respektiva) ajgenvektoro). Tamen, ni povas kompreni kelkaj de la pli plibonigitaj ajgenaj algoritmoj kiel variadoj de pova ripeto. Aldone, iu de la pli bona (algoritmoj, algoritmas) por la ĝeneraligis ajgena problemo estas bazita sur pova ripeto.

Ĉi tiu maniero povas en ĝenerala esti sufiĉe malfrua. Ĝi estas aparte malfrua se estas ajgeno fermi en grandeco al la domina ajgeno.

[redaktu] Plibonigitaj manieroj

Populara maniero por trovanta (ajgenoj, ajgenas) estas la QR algoritmo, kiu estas bazita sur la QR malkomponaĵo. Aliaj plibonigitaj manieroj inkluzivi:

Inversa ripeto
_Rayleigh_ kvocienta ripeto
_Arnoldi_ ripeto
_Lanczos_ ripeto
Jakobia maniero
Duondivigo
Dividi-kaj-(venki, konkeri, venkobati)

Plej ajgenaj algoritmoj fidi unua reduktanta la matrico <_var_>A</_var_> al _Hessenberg_ aŭ tridiagonala (formo, formi). Ĉi tiu estas kutime atingita tra projekcioj.