Дана СЛАУ:
{
a
11
x
1
+
a
12
x
2
+
.
.
.
+
a
1
m
x
m
=
b
1
…
a
m
1
x
1
+
a
m
2
x
2
+
.
.
.
+
a
m
m
x
m
=
b
m
{\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}+...+a_{1m}x_{m}=b_{1}\\\dots \\a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mm}x_{m}=b_{m}\end{cases}}}
A
=
(
a
11
…
a
1
m
⋮
⋱
⋮
a
m
1
…
a
m
m
)
x
=
(
x
1
⋮
x
m
)
b
=
(
b
1
⋮
b
m
)
{\displaystyle A={\begin{pmatrix}a_{11}&\dots &a_{1m}\\\vdots &\ddots &\vdots \\a_{m1}&\dots &a_{mm}\end{pmatrix}}\quad x={\begin{pmatrix}x_{1}\\\vdots \\x_{m}\end{pmatrix}}\quad b={\begin{pmatrix}b_{1}\\\vdots \\b_{m}\end{pmatrix}}}
A
x
=
b
{\displaystyle Ax=b}
A
{\displaystyle A}
⇒
{\displaystyle \Rightarrow }
x
∗
=
(
x
1
∗
…
x
m
∗
)
T
{\displaystyle x^{*}=(x_{1}^{*}\dots x_{m}^{*})^{T}}
e
=
x
−
x
∗
{\displaystyle e=x-x^{*}}
r
=
b
−
A
x
∗
⇒
r
=
A
x
−
A
x
∗
=
A
(
x
−
x
∗
)
⇒
e
=
A
−
1
r
{\displaystyle r=b-Ax^{*}\Rightarrow r=Ax-Ax^{*}=A(x-x^{*})\Rightarrow e=A^{-1}r}
Определение.
‖
x
‖
{\displaystyle \|x\|}
x
{\displaystyle x}
‖
x
‖
≥
0
{\displaystyle \|x\|\geq 0}
‖
x
‖
=
0
⇔
x
=
0
{\displaystyle \|x\|=0\Leftrightarrow x=0}
‖
α
x
‖
=
|
α
|
‖
x
‖
∀
x
∀
α
{\displaystyle \|\alpha x\|=|\alpha |\|x\|\forall x\forall \alpha }
‖
x
+
y
‖
≤
‖
x
‖
+
‖
y
‖
∀
x
,
y
{\displaystyle \|x+y\|\leq \|x\|+\|y\|\forall x,y}
‖
x
‖
1
=
∑
i
=
1
m
|
x
i
|
,
‖
x
‖
2
=
(
∑
i
=
1
m
|
x
i
|
2
)
1
2
,
‖
x
‖
∞
=
max
1
≤
i
≤
m
|
x
i
|
{\displaystyle \|x\|_{1}=\sum _{i=1}^{m}|x_{i}|,\quad \|x\|_{2}=(\sum _{i=1}^{m}|x_{i}|^{2})^{\frac {1}{2}},\quad \|x\|_{\infty }=\max {1\leq i\leq m}|x_{i}|}
Скалярное произведение:
(
x
,
y
)
=
x
1
y
1
+
.
.
.
+
x
m
y
m
{\displaystyle (x,y)=x_{1}y_{1}+...+x_{m}y_{m}}
δ
(
x
∗
)
=
‖
x
−
x
∗
‖
‖
x
‖
{\displaystyle \delta (x^{*})={\frac {\|x-x^{*}\|}{\|x\|}}}
Δ
(
x
∗
)
=
‖
x
−
x
∗
‖
{\displaystyle \Delta (x^{*})=\|x-x^{*}\|}
Определение. Сходимость по норме:
{
x
(
n
)
}
n
=
1
∞
{\displaystyle \{x^{(n)}\}_{n=1}^{\infty }}
x
(
n
)
→
x
{\displaystyle x^{(n)}\to x}
n
→
∞
{\displaystyle n\to \infty }
Δ
(
x
(
n
)
)
=
‖
x
(
n
)
−
x
‖
→
0
{\displaystyle \Delta (x^{(n)})=\|x^{(n)}-x\|\to 0}
n
→
∞
{\displaystyle n\to \infty }
Норма матрицы
‖
A
‖
=
max
x
≠
0
‖
A
x
‖
‖
x
‖
{\displaystyle \|A\|=\max {x\neq 0}{\frac {\|Ax\|}{\|x\|}}}
‖
A
‖
≥
0
‖
A
‖
=
0
⇔
A
=
0
{\displaystyle \|A\|\geq 0\quad \|A\|=0\Leftrightarrow A=0}
‖
α
A
‖
=
|
α
|
‖
A
‖
∀
A
,
α
{\displaystyle \|\alpha A\|=|\alpha |\|A\|\forall A,\alpha }
‖
A
+
B
‖
≤
‖
A
‖
+
‖
B
‖
{\displaystyle \|A+B\|\leq \|A\|+\|B\|}
‖
A
⋅
B
‖
≤
‖
A
‖
⋅
‖
B
‖
{\displaystyle \|A\cdot B\|\leq \|A\|\cdot \|B\|}
‖
A
x
‖
≤
‖
A
‖
⋅
‖
x
‖
(
‖
x
‖
≠
0
⇒
‖
A
x
‖
‖
x
‖
≤
‖
A
‖
−
из определения
)
{\displaystyle \|Ax\|\leq \|A\|\cdot \|x\|\quad (\|x\|\neq 0\Rightarrow {\frac {\|Ax\|}{\|x\|}}\leq \|A\|-{\text{из определения}})}
‖
A
‖
1
=
max
1
≤
j
≤
m
∑
i
=
1
m
|
a
i
j
|
,
‖
A
‖
2
=
max
1
≤
j
≤
m
λ
j
(
A
T
A
)
,
‖
A
‖
∞
=
max
1
≤
j
≤
m
∑
i
=
1
m
|
a
j
i
|
{\displaystyle \|A\|_{1}=\max {1\leq j\leq m}\sum _{i=1}^{m}|a_{ij}|,\quad \|A\|_{2}=\max {1\leq j\leq m}{\sqrt {\lambda _{j}(A^{T}A)}},\quad \|A\|_{\infty }=\max {1\leq j\leq m}\sum _{i=1}^{m}|a_{j}i|}
Это подчиненные нормы
‖
A
‖
E
=
∑
i
,
j
=
1
m
‖
a
i
j
‖
2
{\displaystyle \|A\|_{E}={\sqrt {\sum _{i,j=1}^{m}\|a_{i}j\|^{2}}}}
Обусловленность задачи решения СЛАУ
править
Лемма.
Δ
(
x
∗
)
≤
‖
A
−
1
‖
⋅
‖
r
‖
{\displaystyle \Delta (x^{*})\leq \|A^{-1}\|\cdot \|r\|}
r
=
b
−
A
x
∗
{\displaystyle r=b-Ax^{*}}
Доказательство.
x
−
x
∗
=
e
=
A
−
1
r
⇒
Δ
(
x
∗
)
=
‖
x
−
x
∗
‖
=
‖
A
−
1
r
‖
≤
‖
A
−
1
‖
⋅
‖
r
‖
{\displaystyle x-x^{*}=e=A^{-1}r\Rightarrow \Delta (x^{*})=\|x-x^{*}\|=\|A^{-1}r\|\leq \|A^{-1}\|\cdot \|r\|}
Теорема.
δ
(
x
∗
)
≤
c
o
n
d
(
A
)
⋅
δ
(
b
∗
)
{\displaystyle \delta (x^{*})\leq cond(A)\cdot \delta (b^{*})}
c
o
n
d
(
E
)
=
1
(
E
−
1
=
E
,
‖
E
‖
=
1
)
{\displaystyle cond(E)=1\quad (E^{-1}=E,\|E\|=1)}
c
o
n
d
(
A
)
≥
1
(
E
=
A
−
1
A
,
‖
E
‖
≤
‖
A
−
1
‖
⋅
‖
A
‖
)
{\displaystyle cond(A)\geq 1\quad (E=A^{-1}A,\|E\|\leq \|A^{-1}\|\cdot \|A\|)}
∀
α
≠
0
:
c
o
n
d
(
α
A
)
=
c
o
n
d
(
A
)
(
‖
α
A
‖
⋅
‖
α
A
−
1
‖
=
|
α
|
‖
A
‖
⋅
|
α
|
−
1
‖
A
−
1
‖
)
{\displaystyle \forall \alpha \neq 0:cond(\alpha A)=cond(A)\quad (\|\alpha A\|\cdot \|\alpha A^{-1}\|=|\alpha |\|A\|\cdot |\alpha |^{-1}\|A^{-1}\|)}
Теорема.
x
∗
{\displaystyle x^{*}}
A
∗
x
∗
=
b
{\displaystyle A_{*}x^{*}=b}
A
∗
{\displaystyle A_{*}}
δ
∗
(
x
∗
)
≤
c
o
n
d
(
A
)
⋅
δ
(
A
∗
)
{\displaystyle \delta ^{*}(x^{*})\leq cond(A)\cdot \delta (A_{*})}
δ
∗
(
x
∗
)
=
‖
x
−
x
∗
‖
‖
x
∗
‖
,
δ
(
A
∗
)
=
‖
A
−
A
∗
‖
‖
A
‖
{\displaystyle \delta ^{*}(x^{*})={\frac {\|x-x^{*}\|}{\|x^{*}\|}},\delta (A_{*})={\frac {\|A-A_{*}\|}{\|A\|}}}
Доказательство.
r
=
b
−
A
x
∗
=
A
∗
x
∗
−
A
x
∗
=
(
A
∗
−
A
)
x
∗
{\displaystyle r=b-Ax^{*}=A_{*}x^{*}-Ax^{*}=(A_{*}-A)x^{*}}
δ
∗
(
x
∗
)
=
‖
x
−
x
∗
‖
‖
x
∗
‖
≤
‖
A
−
1
‖
⋅
‖
(
A
∗
−
A
)
x
∗
‖
/
‖
x
∗
‖
≤
‖
a
−
1
‖
⋅
‖
A
∗
−
A
‖
⋅
‖
x
∗
‖
‖
x
∗
‖
=
c
o
n
d
(
A
)
⋅
δ
(
A
∗
)
{\displaystyle \delta ^{*}(x^{*})={\frac {\|x-x^{*}\|}{\|x^{*}\|}}\leq \|A^{-1}\|\cdot \|(A_{*}-A)x^{*}\|/\|x^{*}\|\leq {\frac {\|a^{-1}\|\cdot \|A_{*}-A\|\cdot \|x^{*}\|}{\|x^{*}\|}}=cond(A)\cdot \delta (A_{*})}
Прямой ход:
1-й шаг - пусть
a
11
≠
0
{\displaystyle a_{11}\neq 0}
μ
i
1
=
a
i
1
a
11
,
i
=
2
,
m
¯
{\displaystyle \mu _{i1}={\frac {a_{i1}}{a{11}}},i={\overline {2,m}}}
2..
m
{\displaystyle 2..m}
μ
i
1
{\displaystyle \mu _{i1}}
a
11
x
1
+
a
12
x
2
+
⋯
+
a
1
m
x
m
=
b
1
a
22
(
1
)
x
2
+
⋯
+
a
2
m
(
1
)
x
m
=
b
2
(
1
)
…
a
m
2
(
1
)
x
2
+
⋯
+
a
m
m
(
1
)
x
m
=
b
m
(
1
)
{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1m}x_{m}=b_{1}\\a_{22}^{(1)}x_{2}+\dots +a_{2m}^{(1)}x_{m}=b_{2}^{(1)}\\\dots \\a_{m2}^{(1)}x_{2}+\dots +a_{mm}^{(1)}x_{m}=b_{m}^{(1)}\end{matrix}}}
a
i
j
(
1
)
=
a
i
j
−
μ
i
1
a
i
j
,
b
i
(
1
)
=
b
i
−
μ
i
1
b
1
{\displaystyle a_{ij}^{(1)}=a_{ij}-\mu _{i1}a_{ij},\quad b_{i}^{(1)}=b_{i}-\mu _{i1}b_{1}}
2-й шаг - пусть
a
22
(
1
)
≠
0
,
μ
i
2
=
a
i
2
(
1
)
a
22
(
1
)
{\displaystyle a_{22}^{(1)}\neq 0,\quad \mu _{i2}={\frac {a_{i2}^{(1)}}{a_{22}^{(1)}}}}
k-й шаг:
a
k
k
(
k
−
1
)
≠
0
,
ν
i
k
=
a
i
k
(
k
−
1
)
a
k
k
(
k
−
1
)
,
i
=
k
+
1
,
m
¯
{\displaystyle a_{kk}^{(k-1)}\neq 0,\quad \nu _{ik}={\frac {a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}},i={\overline {k+1,m}}}
За (m-1) шаг получаем:
a
11
x
1
+
a
12
x
2
+
a
33
x
3
+
⋯
+
a
1
m
x
m
=
b
1
a
22
(
1
)
x
2
+
a
33
(
1
)
x
3
+
⋯
+
a
2
m
(
1
)
x
m
=
b
2
(
1
)
a
33
(
2
)
x
3
+
⋯
+
a
2
m
(
2
)
x
m
=
b
2
(
2
)
…
a
m
m
(
m
−
1
)
x
m
=
b
m
(
m
−
1
)
{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+a_{33}x_{3}+\dots +a_{1m}x_{m}=b_{1}\\a_{22}^{(1)}x_{2}+a_{33}^{(1)}x_{3}+\dots +a_{2m}^{(1)}x_{m}=b_{2}^{(1)}\\a_{33}^{(2)}x_{3}+\dots +a_{2m}^{(2)}x_{m}=b_{2}^{(2)}\\\dots \\a_{mm}^{(m-1)}x_{m}=b_{m}^{(m-1)}\end{matrix}}}
Обратный ход:
Из последнего уравнения находим
x
m
{\displaystyle x_{m}}
x
m
−
1
{\displaystyle x_{m-1}}
x
m
=
b
m
(
m
−
1
)
/
a
m
m
(
m
−
1
)
,
x
k
=
(
b
k
(
k
−
1
)
−
a
k
,
k
+
1
(
k
−
1
)
x
k
+
1
−
.
.
.
−
a
k
m
(
k
−
1
)
x
m
)
/
a
k
k
k
−
1
,
k
=
m
−
1
,
1
¯
{\displaystyle x_{m}=b_{m}^{(m-1)}/a_{mm}^{(m-1)},x_{k}=(b_{k}^{(k-1)}-a_{k,k+1}^{(k-1)}x_{k+1}-...-a_{km}^{(k-1)}x_{m})/a_{kk}^{k-1},k={\overline {m-1,1}}}
Трудоемкость:
1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний
⇒
Q
1
=
2
(
m
−
1
)
2
+
3
(
m
−
1
)
{\displaystyle \Rightarrow Q_{1}=2(m-1)^{2}+3(m-1)}
k.
Q
k
=
2
(
m
−
k
)
2
+
3
(
m
−
k
)
{\displaystyle Q_{k}=2(m-k)^{2}+3(m-k)}
Q
=
∑
k
=
1
n
−
1
Q
k
=
2
∑
k
=
1
m
−
1
(
m
−
k
)
2
+
3
∑
k
=
1
m
−
1
(
m
−
k
)
=
2
∑
k
=
1
m
−
1
k
2
+
3
∑
k
=
1
m
−
1
k
=
2
(
m
−
1
)
m
(
2
m
−
1
)
6
+
3
(
m
−
1
)
m
2
≈
2
3
m
3
{\displaystyle Q=\sum _{k=1}^{n-1}Q_{k}=2\sum _{k=1}^{m-1}(m-k)^{2}+3\sum _{k=1}^{m-1}(m-k)=2\sum _{k=1}^{m-1}k^{2}+3\sum _{k=1}^{m-1}k={\frac {2(m-1)m(2m-1)}{6}}+{\frac {3(m-1)m}{2}}\approx {\frac {2}{3}}m^{3}}
Обратный ход:
m
2
{\displaystyle m^{2}}
Матричная форма метода Гаусса. (LU - разложение)
править
После первого шага получаем
A
(
1
)
x
=
b
(
1
)
{\displaystyle A^{(1)}x=b^{(1)}}
M
1
=
(
1
0
0
…
0
−
μ
21
1
0
…
0
−
μ
31
0
1
…
0
…
−
μ
m
1
0
0
…
1
)
M
2
=
(
1
0
0
…
0
0
1
0
…
0
0
−
μ
32
1
…
0
…
0
−
μ
m
2
0
…
1
)
{\displaystyle M_{1}={\begin{pmatrix}1&0&0&\dots &0\\-\mu _{21}&1&0&\dots &0\\-\mu _{31}&0&1&\dots &0\\\dots \\-\mu _{m1}&0&0&\dots &1\end{pmatrix}}M_{2}={\begin{pmatrix}1&0&0&\dots &0\\0&1&0&\dots &0\\0&-\mu _{32}&1&\dots &0\\\dots \\0&-\mu _{m2}&0&\dots &1\end{pmatrix}}}
M
m
−
1
=
(
1
0
…
0
0
0
1
…
0
0
0
0
…
0
0
…
0
0
…
−
μ
m
,
m
−
1
1
)
{\displaystyle M_{m-1}={\begin{pmatrix}1&0&\dots &0&0\\0&1&\dots &0&0\\0&0&\dots &0&0\\\dots \\0&0&\dots &-\mu _{m,m-1}&1\end{pmatrix}}}
A
(
1
)
=
M
1
A
,
b
(
1
)
=
M
1
b
,
A
(
m
−
1
)
=
M
m
−
1
A
(
m
−
2
)
,
b
(
m
−
1
)
=
M
m
−
1
b
(
m
−
2
)
{\displaystyle A^{(1)}=M_{1}A,b^{(1)}=M_{1}b,\quad A^{(m-1)}=M_{m-1}A^{(m-2)},b^{(m-1)}=M_{m-1}b^{(m-2)}}
Начальная система:
M
m
−
1
⋅
.
.
.
⋅
M
2
⋅
M
1
⋅
A
x
=
M
m
−
1
⋅
.
.
.
⋅
M
2
⋅
M
1
⋅
b
{\displaystyle M_{m-1}\cdot ...\cdot M_{2}\cdot M_{1}\cdot Ax=M_{m-1}\cdot ...\cdot M_{2}\cdot M_{1}\cdot b}
M
m
−
1
⋅
.
.
.
⋅
M
2
⋅
M
1
⋅
A
{\displaystyle M_{m-1}\cdot ...\cdot M_{2}\cdot M_{1}\cdot A}
=
A
(
m
−
1
)
{\displaystyle =A^{(m-1)}}
L
=
M
1
−
1
M
2
−
1
.
.
.
M
m
−
1
−
1
=
(
1
0
0
.
.
.
0
μ
21
1
0
.
.
.
0
μ
31
μ
32
1
.
.
.
0
…
μ
m
1
μ
m
2
μ
m
3
.
.
.
1
)
{\displaystyle L=M_{1}^{-1}M_{2}^{-1}...M_{m-1}^{-1}={\begin{pmatrix}1&0&0&...&0\\\mu _{21}&1&0&...&0\\\mu _{31}&\mu _{32}&1&...&0\\\dots \\\mu _{m1}&\mu _{m2}&\mu _{m3}&...&1\end{pmatrix}}}
Свойства элементарных матриц:
det
M
i
=
1
{\displaystyle \det M_{i}=1}
M
i
{\displaystyle M_{i}}
M
i
−
1
{\displaystyle M_{i}^{-1}}
μ
{\displaystyle \mu }
A
=
L
U
{\displaystyle A=LU}
Теорема. Если все главные миноры матрицы
A
≠
0
{\displaystyle A\neq 0}
∃
!
{\displaystyle \exists !}
L
{\displaystyle L}
(
1
)
{\displaystyle (1)}
U
{\displaystyle U}
A
=
L
U
{\displaystyle A=LU}
Использование:
преобразуем
b
{\displaystyle b}
b
(
m
−
1
)
b
(
m
−
1
)
=
M
m
−
1
.
.
.
M
2
M
1
b
{\displaystyle b^{(m-1)}\quad b^{(m-1)}=M_{m-1}...M_{2}M_{1}b}
Решаем систему
U
x
=
b
(
m
−
1
)
{\displaystyle Ux=b^{(m-1)}}
Количество действий:
2
3
m
3
+
2
m
2
{\displaystyle {\frac {2}{3}}m^{3}+2m^{2}}
Модификации Гаусса
править
на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент
a
i
k
,
k
{\displaystyle a_{i_{k},k}}
на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами
i
=
k
.
.
m
{\displaystyle i=k..m}
Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.
Метод Холецкого
править
A
x
=
b
{\displaystyle Ax=b}
A
{\displaystyle A}
A
=
A
T
{\displaystyle A=A^{T}}
∀
x
≠
0
:
(
A
x
,
x
)
>
0
{\displaystyle \forall x\neq 0:(Ax,x)>0}
A
x
{\displaystyle Ax}
x
{\displaystyle x}
Все главные миноры положительны
|
a
i
i
|
>
∑
j
≠
i
|
a
i
j
|
{\displaystyle |a_{ii}|>\sum _{j\neq i}|a_{ij}|}
|
a
j
j
|
>
∑
i
≠
j
|
a
i
j
|
{\displaystyle |a_{jj}|>\sum _{i\neq j}|a_{ij}|}
Специальное
L
U
{\displaystyle LU}
A
=
L
L
T
{\displaystyle A=LL^{T}}
L
=
(
l
11
0
…
0
l
21
l
22
…
0
…
l
m
1
l
m
2
…
l
m
m
)
{\displaystyle L={\begin{pmatrix}l_{11}&0&\dots &0\\l_{21}&l_{22}&\dots &0\\\dots \\l_{m1}&l_{m2}&\dots &l_{mm}\end{pmatrix}}}
l
11
2
=
a
11
l
i
1
l
11
=
a
i
1
i
=
2
,
m
¯
l
21
2
+
l
22
2
=
a
i
2
l
i
1
l
21
+
l
i
2
l
22
=
a
i
2
i
=
3
,
m
¯
…
l
k
1
2
+
l
k
2
2
+
.
.
.
+
l
k
k
2
=
a
k
k
l
i
1
l
k
1
+
.
.
.
+
l
i
k
l
k
k
=
a
i
k
i
=
k
+
1
,
m
¯
…
l
m
1
2
+
.
.
.
+
l
m
m
2
=
a
m
m
⇒
{\displaystyle {\begin{matrix}&l_{11}^{2}=a_{11}&\\&l_{i1}l_{11}=a_{i1}&i={\overline {2,m}}\\&l_{21}^{2}+l_{22}^{2}=a_{i2}&\\&l_{i1}l_{21}+l_{i2}l_{22}=a_{i2}&i={\overline {3,m}}\\&\dots &\\&l_{k1}^{2}+l_{k2}^{2}+...+l_{kk}^{2}=a_{kk}&\\&l_{i1}l_{k1}+...+l_{ik}l_{kk}=a_{ik}&i={\overline {k+1,m}}\\&\dots &\\&l_{m1}^{2}+...+l_{mm}^{2}=a_{mm}&\end{matrix}}\Rightarrow }
⇒
l
11
=
a
11
l
i
1
=
a
i
1
/
l
11
i
=
2
,
m
¯
l
22
=
a
i
2
−
l
21
2
l
i
2
=
(
a
i
2
−
l
i
1
l
21
)
/
l
22
i
=
3
,
m
¯
…
l
k
k
=
a
k
k
−
l
k
1
2
−
.
.
.
−
l
k
,
k
−
1
2
l
i
k
=
(
a
i
k
−
l
i
1
l
k
1
−
.
.
.
−
l
i
,
k
−
1
l
k
,
k
−
1
)
/
l
k
k
i
=
k
+
1
,
m
¯
…
l
m
m
=
a
m
m
−
l
m
1
2
−
.
.
.
−
l
m
,
m
−
1
2
{\displaystyle \Rightarrow {\begin{matrix}&l_{11}={\sqrt {a_{11}}}&\\&l_{i1}=a_{i1}/l_{11}&i={\overline {2,m}}\\&l_{22}={\sqrt {a_{i2}-l_{21}^{2}}}&\\&l_{i2}=(a_{i2}-l_{i1}l_{21})/l_{22}&i={\overline {3,m}}\\&\dots &\\&l_{kk}={\sqrt {a_{kk}-l_{k1}^{2}-...-l_{k,k-1}^{2}}}&\\&l_{ik}=(a_{ik}-l_{i1}l_{k1}-...-l_{i,k-1}l_{k,k-1})/l_{kk}&i={\overline {k+1,m}}\\&\dots &\\&l_{mm}={\sqrt {a_{mm}-l_{m1}^{2}-...-l_{m,m-1}^{2}}}&\end{matrix}}}
После получения этого разложения решаем
L
y
=
b
,
L
T
x
=
y
{\displaystyle Ly=b,L^{T}x=y}
2
m
2
{\displaystyle 2m^{2}}
Метод Прогонки
править
b
1
x
1
+
c
1
x
2
=
d
1
a
2
x
1
+
b
2
x
2
+
c
2
x
3
=
d
2
…
a
i
x
i
−
1
+
b
i
x
i
+
c
i
x
i
+
1
=
d
i
…
a
m
−
1
x
m
−
2
+
b
m
−
1
x
m
−
1
+
c
m
−
1
x
m
=
d
m
−
1
a
m
x
m
−
1
+
b
m
x
m
=
d
m
{\displaystyle {\begin{matrix}&b_{1}x_{1}+c_{1}x_{2}&=d_{1}\\&a_{2}x_{1}+b_{2}x_{2}+c_{2}x_{3}&=d_{2}\\&\dots \\&a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}&=d_{i}\\&\dots \\&a_{m-1}x_{m-2}+b_{m-1}x_{m-1}+c_{m-1}x_{m}&=d_{m-1}\\&a_{m}x_{m-1}+b_{m}x_{m}&=d_{m}\\\end{matrix}}}
Вывод:
x
1
=
α
1
x
2
+
β
1
α
1
=
−
c
1
b
1
β
1
=
d
1
b
1
x
2
=
α
2
x
3
+
β
2
α
2
=
−
c
2
b
2
+
a
2
α
1
β
2
=
d
2
−
a
2
β
1
b
2
+
a
2
α
1
…
x
i
=
α
i
x
i
+
1
+
β
i
α
i
=
−
c
i
b
i
+
a
i
α
i
−
1
β
i
=
d
i
−
a
i
β
i
−
1
b
i
+
a
i
α
i
−
1
…
x
m
−
1
=
α
m
−
1
x
m
+
β
m
m
−
1
{\displaystyle {\begin{matrix}x_{1}=\alpha _{1}x_{2}+\beta _{1}\alpha _{1}=-{\frac {c_{1}}{b_{1}}}\beta _{1}={\frac {d_{1}}{b_{1}}}\\x_{2}=\alpha _{2}x_{3}+\beta _{2}\alpha _{2}=-{\frac {c_{2}}{b_{2}+a_{2}\alpha _{1}}}\beta _{2}={\frac {d_{2}-a_{2}\beta _{1}}{b_{2}+a_{2}\alpha _{1}}}\\\dots \\x_{i}=\alpha _{i}x_{i+1}+\beta _{i}\alpha _{i}=-{\frac {c_{i}}{b_{i}+a_{i}\alpha _{i-1}}}\beta _{i}={\frac {d_{i}-a_{i}\beta _{i-1}}{b_{i}+a_{i}\alpha _{i-1}}}\\\dots \\x_{m-1}=\alpha _{m-1}x_{m}+\beta _{mm-1}\end{matrix}}}
m
:
a
m
(
a
m
−
1
x
m
+
β
m
−
1
)
+
b
m
x
m
⇒
x
m
=
β
m
=
d
m
−
a
m
β
m
−
1
b
m
+
a
m
α
m
−
1
{\displaystyle m:a_{m}(a_{m-1}x_{m}+\beta _{m-1})+b_{m}x_{m}\Rightarrow x_{m}=\beta _{m}={\frac {d_{m}-a_{m}\beta _{m-1}}{b_{m}+a_{m}\alpha _{m-1}}}}
Алгоритм
Прямой ход:
α
i
=
−
c
i
γ
i
β
i
=
d
i
γ
i
γ
i
=
b
i
,
i
=
1
;
α
i
=
−
c
i
γ
i
β
i
=
d
i
−
a
i
β
i
−
1
γ
i
γ
i
=
b
i
+
a
i
α
i
−
1
,
i
=
2..
m
−
1
;
β
i
=
d
i
−
a
i
β
i
−
1
γ
i
γ
i
=
b
i
+
a
i
α
i
−
1
,
i
=
m
.
{\displaystyle {\begin{aligned}\alpha _{i}&=-{\frac {c_{i}}{\gamma _{i}}}\beta _{i}={\frac {d_{i}}{\gamma _{i}}}\gamma _{i}=b_{i},&i=1;&\\\alpha _{i}&=-{\frac {c_{i}}{\gamma _{i}}}\beta _{i}={\frac {d_{i}-a_{i}\beta _{i-1}}{\gamma _{i}}}\gamma _{i}=b_{i}+a_{i}\alpha _{i-1},&i=2..m-1;&\\\beta _{i}&={\frac {d_{i}-a_{i}\beta _{i-1}}{\gamma _{i}}}\gamma _{i}=b_{i}+a_{i}\alpha _{i-1},&i=m.&\end{aligned}}}
Обратный ход:
i
=
m
x
m
=
b
m
i
=
m
−
1..1
x
i
=
a
i
x
i
+
1
+
β
i
{\displaystyle {\begin{matrix}i=m&x_{m}=b_{m}\\i=m-1..1&x_{i}=a_{i}x_{i+1}+\beta _{i}\\\end{matrix}}}
Количество операций:
Q
=
8
m
{\displaystyle Q=8m}
Теорема. Пусть
|
b
k
|
≥
|
a
k
|
+
|
c
k
|
,
|
b
k
′
|
>
|
a
k
|
,
(
1
≤
k
≤
m
)
{\displaystyle |b_{k}|\geq |a_{k}|+|c_{k}|,|b'_{k}|>|a_{k}|,(1\leq k\leq m)}
γ
i
≠
0
{\displaystyle \gamma _{i}\neq 0}
α
i
≤
1
{\displaystyle \alpha _{i}\leq 1}
∀
i
=
1
,
2
,
.
.
.
,
m
{\displaystyle \forall i=1,2,...,m}
