Ітераційні методи розв'язування СЛАР

Шаблон:Вичитати Ітераційні методи або ж методи ітерацій розв'язування СЛАР — наближені методи розв'язку проблеми знаходження власних значень та власних векторів (що еквівалентно розв'язку СЛАР), які базуються на покроковому наближені (знаходження за наближеним значенням величини наступного наближення) до їх точних значень, оминаючи обчислення характеристичного многочлена. Ітераційні методи дозволяють отримати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів (ітераційний процес). Характер збіжності й сам факт збіжності методу залежить від вибору початкового (нульового) наближення, кореня ${\overrightarrow{x}}_0$.

Ці методи є чисельними, вони суттєво відрізняються для матриць середнього і великого розміру, бо методи для невеликих матриць зазвичай є такими, що руйнують розрідженість матриць (її заповненість в основному нулями), відтак такі матриці більше не можуть бути збережені в пам'яті обчислювальної машини компактно.

Методи, які не зберігають розрідженості

Метод Якобі

Опис методу

$\{\begin{array}{c}{a}_{11}{x}_1+\cdots +a_{1n}{x}_n=b_1\\ ⋮\\ a_{n1}{x}_1+\cdots +a_{nn}{x}_n=b_n\end{array}$

АХ = В — у матричному вигляді. $\mathrm{A}=\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1n}\\ ⋮& & ⋮\\ a_{n1}& \cdots & a_{nn}\end{array}\right];\mathrm{X}=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right];\mathrm{B}=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_n\end{array}\right]$

Припускаючи, що $a_{ii}\ne 0$ ; ($i$$=$$1$,$2$, …, $n$), виразимо $x_1$ через перше рівняння, $x_2$ — через друге і т. д. $\{\begin{array}{c}{x}_1=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}{x}_2-\cdots -\frac{a_{1n}}{a_{11}}{x}_n\\ ⋮\\ x_n=\frac{b_n}{a_{nn}}-\frac{a_{1n}}{a_{nn}}{x}_1-\frac{a_{2n}}{a_{nn}}{x}_2-\cdots -\frac{a_{n-1,n}}{a_{nn}}{x}_{n-1}\end{array}$ Позначимо:

$\frac{b_i}{a_{ii}}={\beta }_i;-\frac{a_{ij}}{a_{ii}}={\alpha }_{ij};$

$i$$=$$1$,$2$,…,$n$; $j$$=$$1$,$2$,…,$n$; $\{\begin{array}{c}{x}_1={\beta }_1+{\alpha }_{12}{x}_2+\cdots +{\alpha }_{1n}{x}_n\\ ⋮\\ x_n={\beta }_n+{\alpha }_{n1}{x}_1+\cdots +{\alpha }_{n,n-1}{x}_{n-1}\end{array}$ Система приведена до нормального вигляду.

$\alpha =\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right];\beta =\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]$

$X$=$\beta$+$\alpha$х — система у матричному вигляді.

За нульове наближення приймемо стовпець вільних членів.

$\left[\begin{array}{c}{x}_1^{(0)}\\ ⋮\\ x_n^{(0)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]$ — нульове наближення;

$\left[\begin{array}{c}{x}_1^{(1)}\\ ⋮\\ x_n^{(1)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]+\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1^{(0)}\\ ⋮\\ x_n^{(0)}\end{array}\right]$ — I наближення;

$\left[\begin{array}{c}{x}_1^{(2)}\\ ⋮\\ x_n^{(2)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]+\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1^{(1)}\\ ⋮\\ x_n^{(1)}\end{array}\right]$ — II наближення і т. д.;

$X^{(k)}=\beta +\alpha X^{(k-1)}$ ($k$$=$$0$, …,$\pi$).

$X=\underset{x\to \mathrm{\infty }}{\lim }{x}^{(k)}$ — розв'язання системи.

Умови збіжності процесу

Метод ітерації застосовують у випадку, якщо сходиться послідовність наближень по вказаному алгоритму. Умови збіжності : $\sum _{j=1}^n|{\alpha }_{ij}|<1$ (де $i$$=$$1$, $2$, …, $n$) або $\sum _{i=1}^n|{\alpha }_{ij}|<1$ (де $j$$=$$1$, $2$, …, $n$;).

Оцінка похибки

$\Vert x_i-x_i^{(k)}\Vert \le \frac{\Vert \alpha {\Vert }^{k+1}}{1-\Vert \alpha \Vert }\times \Vert \beta \Vert \le \epsilon$, де $\epsilon$ -точність, $x_i$ — вектор точних значень.

$\Vert \alpha \Vert$ — одна з трьох норм матриці $\alpha$,$\Vert \beta \Vert$ — одна з трьох норм матриці $\beta$.

QR-метод

Шаблон:Main Належить до класу т. зв. степеневих алгоритмів, є одним з найефективніших серед них для не надто великих матриць. Ітерація відбувається за наступною схемою:

$A_k=Q_k{R}_k,A_{k+1}=R_k{Q}_k$

Тут $Q_k$ є ортогональною або унітарною матрицею, а $R_k$ є правою трикутною матрицею. Таким чином, для переходу до наступного кроку ітерації (від $A_k$ до $A_{k+1}$) спочатку знаходиться ортогонально-трикутний розклад матриці $A_k$, після чого матриці $Q_k$ і $R_k$ перемножуються в оберненому порядку.

Методи, які зберігають розрідженість

Основними для задач високого порядку (тисячі, десятки тисяч рядків і стовпців) є методи, елементарна операція яких — перемноження матриці на вектор. Припустимо, що власні значення матриці занумеровані спадними за модулем ($|{\lambda }_1|\ge |{\lambda }_2|\ge ...\ge |{\lambda }_n|$). Найбільш широку область застосування має степеневий метод для обчислення власного значення, найбільшого за модулем, $|{\lambda }_1|$. Виходячи з початкового наближення ${\overrightarrow{x}}_0$ будується послідовність нормованих векторів:

${\overrightarrow{x}}_{k+1}={\rho }_{k}A{x}_k,{\rho }_k=1/||A{x}_k||$

Така послідовність збігається якщо:

1. всі елементарні дільники матриці $A$, що відносяться до ${\lambda }_1$ — лінійні,
2. немає інших власних значень з таким модулем,
3. у розкладі нульового наближення ${\overrightarrow{x}}_0$ за кореневим базисом $A$ присутня нетривіальна компонента за власним підпростором ${\lambda }_1$.

Збіжність в цьому методі не надто швидка, як правило, і визначається відношенням двох старших по модулю власних значень.

Важливими є також метод обернених ітерацій та метод Стюарта, що теж визначають власні значення по одному. Для одночасного їх пошуку існує метод Ланцоша.

Див. також

• Метод ітерації (алгоритм)

Джерела

• Шаблон:Книга
• Даніліна Н. І., Дубровська Н. С., Кваша О. П., Смирнов Г. Л., Феклісов Г. І. «Чисельні методи: Посібник для технікумів.» Видання «Вища школа»,1976