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

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

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

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

Метод Якобі

Докладніше: Метод обертання Якобі

Докладніше: Метод Якобі

Опис методу

${\displaystyle \left\{{\begin{array}{c}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1}\\\vdots \\a_{n1}x_{1}+\cdots +a_{nn}x_{n}=b_{n}\end{array}}\right.}$

АХ = В — у матричному вигляді. ${\displaystyle \mathrm {A} ={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &&\vdots \\a_{n1}&\cdots &a_{nn}\end{bmatrix}};\qquad \mathrm {X} ={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}};\qquad \mathrm {B} ={\begin{bmatrix}b_{1}\\\vdots \\b_{n}\end{bmatrix}}}$

Припускаючи, що ${\displaystyle a_{ii}\neq 0}$ ; (${\displaystyle i}$${\displaystyle =}$${\displaystyle 1}$,${\displaystyle 2}$, …, ${\displaystyle n}$), виразимо ${\displaystyle x_{1}}$ через перше рівняння, ${\displaystyle x_{2}}$ — через друге і т. д. ${\displaystyle \left\{{\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}\\\vdots \\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}}\right.}$ Позначимо:

${\displaystyle {\frac {b_{i}}{a_{ii}}}=\beta _{i};-{\frac {a_{ij}}{a_{ii}}}=\alpha _{ij};}$

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

${\displaystyle \alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &&\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}};\qquad \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}}$

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

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

${\displaystyle {\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}}$ — нульове наближення;

${\displaystyle {\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &&\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}}$ — I наближення;

${\displaystyle {\begin{bmatrix}x_{1}^{(2)}\\\vdots \\x_{n}^{(2)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &&\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}}$ — II наближення і т. д.;

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

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

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

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

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

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

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

QR-метод

Докладніше: QR-алгоритм

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

${\displaystyle A_{k}=Q_{k}R_{k},\qquad A_{k+1}=R_{k}Q_{k}}$

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

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

Основними для задач високого порядку (тисячі, десятки тисяч рядків і стовпців) є методи, елементарна операція яких — перемноження матриці на вектор. Припустимо, що власні значення матриці занумеровані спадними за модулем (${\displaystyle |\lambda _{1}|\geq |\lambda _{2}|\geq ...\geq |\lambda _{n}|}$). Найбільш широку область застосування має степеневий метод для обчислення власного значення, найбільшого за модулем, ${\displaystyle |\lambda _{1}|}$. Виходячи з початкового наближення ${\displaystyle {\vec {x}}_{0}}$ будується послідовність нормованих векторів:

${\displaystyle {\vec {x}}_{k+1}=\rho _{k}Ax_{k},\qquad \rho _{k}=1/||Ax_{k}||}$

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

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

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

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

Див. також

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

Джерела

• И. М. Виноградов. Математическая энциклопедия. Том 2. — М. : «Советская энциклопедия», 1985. — Т. 2. — С. 686-689.
• Даніліна Н. І., Дубровська Н. С., Кваша О. П., Смирнов Г. Л., Феклісов Г. І. «Чисельні методи: Посібник для технікумів.» Видання «Вища школа»,1976