Численные Методы, 05 лекция (от 27 февраля)
Материал из eSyr's wiki.
(Различия между версиями)
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1272 участника 88.191.57.15 (обсуждение)) |
||
| Строка 1: | Строка 1: | ||
| - | == | + | [[Численные Методы, 04 лекция (от 20 февраля)|Предыдущая лекция]] | [[Численные Методы, 06 лекция (от 05 марта)|Следующая лекция]] |
| - | + | ||
| - | + | = Глава 1. Численные методы линейной алгебры = | |
| - | + | == Параграф 6. Теоремы о сходимости итерационных методов == | |
| + | |||
| + | '''Следствие 4'''. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме. | ||
| + | |||
| + | '''Доказательство.''' | ||
| + | * метод Зейделя: (D + R<sub>1</sub>)<sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f | ||
| + | * B − 0,5τA > 0, τ = 1 | ||
| + | * D + R<sub>1</sub> = B, τ = 1 | ||
| + | * D + R<sub>1</sub> > <sup>1</sup>/<sub>2</sub> (R<sub>1</sub> + D + R<sub>2</sub>) | ||
| + | * 2D + 2R<sub>1</sub> > R<sub>1</sub> + D + R<sub>2</sub> | ||
| + | * D + R<sub>1</sub> − R<sub>2</sub> > 0 | ||
| + | * ((D + R<sub>1</sub> − R<sub>2</sub>)x, x) > 0 | ||
| + | * (Dx, x) + (R<sub>1</sub>x, x) − (R<sub>2</sub>x, x) > 0 ⇒ (Dx, x) > 0 | ||
| + | * R<sub>1</sub> = R<sub>2</sub>* | ||
| + | * R<sub>2</sub> = R<sub>1</sub>* | ||
| + | * a<sub>ii</sub> > 0, i = <span style="border-top:solid 1px">1, m</span> | ||
| + | * (R<sub>1</sub>x, x) = (x, R<sub>1</sub>*x) = (xR<sub>2</sub>, x) = (R<sub>2</sub>x, x) | ||
| + | |||
| + | чтд | ||
| + | |||
| + | == Параграф 7. Оценка скорости сходимости итерационных методов == | ||
| + | |||
| + | * Ax = f (1) | ||
| + | * |A| ≠ 0, A ∈ ℝ<sup>m × m</sup> | ||
| + | * B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f, n ∈ ℕ ∪ {0} (2) | ||
| + | * x<sup>0</sup> задано | ||
| + | * v<sup>n</sup> = x<sup>n</sup> − x — погрешность | ||
| + | * B <sup>(v<sup>n + 1</sup> − v<sup>n</sup>)</sup>/<sub>τ</sub> + Av<sup>n</sup> = 0, n ∈ ℕ ∪ {0} (3) | ||
| + | * v<sup>0</sup> = x<sup>0</sup> − x | ||
| + | |||
| + | Если в какой-либо норме удаётся получить оценку вида | ||
| + | * ||v<sup>n + 1</sup>|| ≤ ρ||v<sup>n</sup>||, 0 < ρ < 1 (4) | ||
| + | то ||v<sup>n</sup>|| ≤ ρ<sup>n</sup>||v<sup>0</sup>|| → 0 при n → ∞ | ||
| + | |||
| + | * ||x<sup>n</sup> − x|| ≤ ρ<sup>n</sup>||x<sup>0</sup> − x|| | ||
| + | * ||x<sup>n</sup> − x|| ≤ ε||x<sup>0</sup> − x|| | ||
| + | * ρ<sup>n</sup> ≤ ε | ||
| + | * <sup>1</sup>/<sub>ε</sub> ≤ (<sup>1</sup>/<sub>ρ</sub>)<sup>n</sup> | ||
| + | * n ln <sup>1</sup>/<sub>ρ</sub> ≥ ln <sup>1</sup>/<sub>ε</sub> | ||
| + | * n ≥ n<sub>0</sub>(ε) = [<sup>ln <sup>1</sup>/<sub>ε</sub></sup>/<sub>ln <sup>1</sup>/<sub>ρ</sub></sub>] | ||
| + | |||
| + | ln <sup>1</sup>/<sub>ρ</sub> — скорость сходимости итерационного метода | ||
| + | |||
| + | Пусть H — вещественное пространство, dim H = m | ||
| + | * ∀ x, y ∈ H (x, y) = ∑<sub>i = 1</sub><sup>m</sup>x<sub>i</sub>y<sub>i</sub> | ||
| + | * ||x|| = (∑<sub>i = 1</sub><sup>m</sup> x<sub>i</sub><sup>2</sup>)<sup><sup>1</sup>/<sub>2</sub></sup> | ||
| + | |||
| + | Пусть B = B* > 0 | ||
| + | |||
| + | Энергетическая норма ||x||<sub>B</sub> = (Bx,x)<sup><sup>1</sup>/<sub>2</sub></sup> | ||
| + | |||
| + | '''Теорема 4 (об оценке скорости сходимости итерационного метода)'''. Пусть | ||
| + | * A = A* > 0 | ||
| + | * B = B* > 0 | ||
| + | * 0 < ρ < 1 | ||
| + | * <sup>1 − ρ</sup>/<sub>τ</sub>B ≤ A ≤ <sup>1 + ρ</sup>/<sub>τ</sub>B (5) | ||
| + | Тогда итерационный метод (2) сходится к решению СЛАУ (1) и имеет место оценка ||v<sup>n + 1</sup>||<sub>B</sub> ≤ ρ||v<sup>n</sup>|| (6) | ||
| + | |||
| + | '''Доказательство.''' | ||
| + | Сходимость: | ||
| + | * A ≤ <sup>1 + ρ</sup>/<sub>τ</sub>B | ||
| + | * A < <sup>2</sup>/<sub>τ</sub>B | ||
| + | * B − 0,5τA > 0 | ||
| + | |||
| + | Оценки: | ||
| + | * B <sup>(v<sup>n + 1</sup> − v<sup>n</sup>)</sup>/<sub>τ</sub> + Av<sup>n</sup> = 0 (*) | ||
| + | * ∃ B<sup>½</sup>, B<sup>−½</sup>, B<sup>½</sup> = (B<sup>½</sup>)* > 0 | ||
| + | |||
| + | умножим (*) на B<sup>−½</sup> слева: | ||
| + | * B<sup>½</sup> <sup>(v<sup>n + 1</sup> − v<sup>n</sup>)</sup>/<sub>τ</sub> + B<sup>−½</sup>Av<sup>n</sup> = 0 | ||
| + | * z<sup>n</sup> = B<sup>½</sup>v<sup>n</sup> | ||
| + | * v<sup>n</sup> = B<sup>−½</sup>z<sup>n</sup> | ||
| + | * <sup>z<sup>n + 1</sup> − z<sup>n</sup></sup>/<sub>τ</sub> + B<sup>−½</sup>AB<sup>−½</sup>z<sup>n</sup> = 0 | ||
| + | * z<sup>n + 1</sup> = z<sup>n</sup> & minus; τB<sup>−½</sup>AB<sup>−½</sup>z<sup>n</sup> = (E − τB<sup>−½</sup>AB<sup>−½</sup>)z<sup>n</sup> = Sz<sup>n</sup> | ||
| + | ** S = E − τB<sup>−½</sup>AB<sup>−½</sup> (7) | ||
| + | * ||z<sup>n</sup>||<sup>2</sup> = (z<sup>n</sup>, z<sup>n</sup>) = (B<sup>½</sup>v<sup>n</sup>, B<sup>½</sup>v<sup>n</sup>) = (Bv<sup>n</sup>, v<sup>n</sup>) = ||v<sup>n</sup>||<sub>B</sub> | ||
| + | |||
| + | Покажем, что S — самосопряжённая: | ||
| + | * S* = E − τB<sup>−½</sup>AB<sup>−½</sup> | ||
| + | |||
| + | <div style="border:dotted 1px; background-color:#eee; font-size:90%; float:right; width:240px; padding:4px; margin:4px">'''Равенство Парсиваля''' | ||
| + | Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑<sub>k = 1</sub><sup>m</sup>c<sub>k</sub>e<sub>k</sub>. | ||
| + | |||
| + | Тогда равенство Парсиваля есть ||x||<sup>2</sup> = ∑<sub>k = 1</sub><sup>m</sup>c<sub>k</sub><sup>2</sup></div> | ||
| + | # Покажем, что все собственные значения матрицы S по модулю не превосходят ρ | ||
| + | #: Пусть s<sub>k</sub> — собственное значение, k = <span style="border-top:solid 1px">1, m</span> | ||
| + | #:* (E − τB<sup>−½</sup>AB<sup>−½</sup>)x = s<sub>k</sub>x, x ≠ 0 | ||
| + | #: Домножим на B<sup>½</sup> слева: | ||
| + | #:* (B<sup>½</sup> − τAB<sup>−½</sup>)x = s<sub>k</sub>B<sup>½</sup>x | ||
| + | #:* y = B<sup>−½</sup>x | ||
| + | #:* x = B<sup>½</sup>)y | ||
| + | #:* (B − τA)y = s<sub>k</sub>By | ||
| + | #:* τAy = (1 − s<sub>k</sub>)By | ||
| + | #:* Ay = <sup>(1 − s<sub>k</sub>)</sup>/<sub>τ</sub>By | ||
| + | #: Применим оценку (5): | ||
| + | #:* <sup>1 − ρ</sup>/<sub>τ</sub>(By, y) ≤ (Ay, y) = <sup>(1 − s<sub>k</sub>)</sup>/<sub>τ</sub>By ≤ <sup>1 + ρ</sup>/<sub>τ</sub>(By, y) | ||
| + | #:* (By, y) ≥ 0 | ||
| + | #:* 1 − ρ ≤ 1 − s<sub>k</sub> ≤ 1 + ρ ⇒ |s<sub>k</sub>| < ρ, k = <span style="border-top:solid 1px">1, m</span> | ||
| + | # S = S* | ||
| + | #:* {e<sub>k</sub>} — ортонормированный базис из собственных векторов S | ||
| + | #:* S<sub>e<sub>k</sub></sub> = s<sub>k</sub>e<sub>k</sub>? k = <span style="border-top:solid 1px">1, m</span> | ||
| + | #:* z<sup>n</sup> = ∑<sub>k = 1</sub><sup>m</sup>c<sub>k</sub><sup>(n)</sup>e<sub>k</sub> | ||
| + | #:* z<sup>n + 1</sup> = Sz<sup>n</sup> = ∑<sub>k = 1</sub><sup>m</sup>s<sub>k</sub>c<sub>k</sub><sup>(n)</sup>e<sub>k</sub> | ||
| + | #:* ||z<sup>n + 1</sup>||<sup>2</sup> = ∑<sub>k = 1</sub><sup>m</sup>s<sub>k</sub><sup>2</sup>(c<sub>k</sub><sup>(n)</sup>)<sup>2</sup> | ||
| + | #:* ||z<sup>n + 1</sup>||<sup>2</sup> ≤ ρ<sup>2</sup>∑<sub>k = 1</sub><sup>m</sup>(c<sub>k</sub><sup>(n)</sup>)<sup>2</sup> = ρ<sup>2</sup>||z<sup>n</sup>||<sup>2</sup> | ||
| + | #:* ||z<sup>n + 1</sup>|| ≤ ρ||z<sup>n</sup>|| | ||
| + | #:* ||v<sup>n + 1</sup>||<sub>B</sub> ≤ ρ||v<sup>n</sup>||<sub>B</sub> | ||
| + | |||
| + | чтд | ||
| + | |||
| + | '''Следствие 1.''' | ||
| + | * A = A* > 0 | ||
| + | * B = B* > 0 | ||
| + | * 0 < ρ < 1 | ||
| + | * ∃ γ<sub>1</sub> > 0, γ<sub>2</sub> > 0: γ<sub>1</sub>B ≤ A ≤ γ<sub>2</sub>B (8) | ||
| + | Тогда | ||
| + | * τ = τ<sub>0</sub> = <sup>2</sup>/<sub>γ<sub>1</sub> + γ<sub>2</sub></sub>, ρ = <sup>1 − ξ</sup>/<sub>1 + ξ</sub>, ξ = <sup>γ<sub>1</sub></sup>/<sub>γ<sub>2</sub></sub> | ||
| + | |||
| + | [[Изображение:Ildar.jpg|thumb|«Ионкин всегда доказывает условие исходя из следствия». Ильдар.]] | ||
| + | '''Доказательство:''' | ||
| + | |||
| + | * <sup>1 − ρ</sup>/<sub>τ</sub> = γ<sub>1</sub> | ||
| + | * <sup>1 + ρ</sup>/<sub>τ</sub> = γ<sub>2</sub> | ||
| + | * <sup>2</sup>/<sub>τ</sub> = γ<sub>1</sub> + γ<sub>2</sub> | ||
| + | * τ = <sup>2</sup>/<sub>γ<sub>1</sub> + γ<sub>2</sub></sub> | ||
| + | * γ<sub>1</sub> − γ<sub>2</sub> = <sup>2ρ</sup>/<sub>τ</sub> = ρ(γ<sub>1</sub> + γ<sub>2</sub>) | ||
| + | * ρ = <sup>γ<sub>1</sub> − γ<sub>2</sub></sup>/<sub>γ<sub>1</sub> + γ<sub>2</sub></sub> = <sup>1 − <sup>γ<sub>1</sub></sup>/<sub>γ<sub>2</sub></sub></sup>/<sub>1 + <sup>γ<sub>1</sub></sup>/<sub>γ<sub>2</sub></sub></sub> = <sup>1 − ξ</sup>/<sub>1 + ξ</sub> | ||
| + | |||
| + | '''Следствие 2.''' Пусть A = a* > 0, | ||
| + | * γ<sub>1</sub> = min<sub>1 ≤ k ≤ m</sub> λ<sub>k</sub><sup>A</sup>, > 0 в силу положительной определённости | ||
| + | * γ<sub>2</sub> = max<sub>1 ≤ k ≤ m</sub> λ<sub>k</sub><sup>A</sup> | ||
| + | |||
| + | Тогда МПИ (x<sup>n+1</sup> − x<sup>n</sup>)/τ + Ax<sup>n</sup> = f, где τ = <sup>2</sup>/<sub>γ<sub>1</sub> + γ<sub>2</sub></sub>, ρ = <sup>1 − ξ</sup>/<sub>1 + ξ</sub>, ξ = <sup>γ<sub>1</sub></sup>/<sub>γ<sub>2</sub></sub> — сходится, имеет место оценка ||x<sup>n</sup> − x|| ≤ ρ||x<sup>n</sup> − x|| | ||
| + | |||
| + | '''Доказательство.''' аналогично Следствию 1. | ||
| + | |||
| + | == Параграф 8. Исследование сходимости ПТИМ == | ||
| + | * Ax = f (1) | ||
| + | * |A| ≠ 0, A ∈ ℝ<sup>m × m</sup> | ||
| + | * A = R<sub>1</sub> + R<sub>2</sub>, | ||
| + | {|style="text-align:center" | ||
| + | | | ||
| + | {| | ||
| + | |rowspan = "3"|R<sub>1</sub> = ( | ||
| + | |<sup>a<sub>11</sub></sup>/<sub>2</sub> | ||
| + | |… | ||
| + | |a<sub>ij</sub> | ||
| + | |rowspan = "3"|) | ||
| + | |- | ||
| + | |colspan="3"|⋱ | ||
| + | |- | ||
| + | |0 | ||
| + | |… | ||
| + | |<sup>a<sub>mm</sub></sup>/<sub>2</sub> | ||
| + | |} | ||
| + | | | ||
| + | {| | ||
| + | |rowspan = "3"|R<sub>2</sub> = ( | ||
| + | ||<sup>a<sub>11</sub></sup>/<sub>2</sub> | ||
| + | |… | ||
| + | |0 | ||
| + | |rowspan = "3"|) | ||
| + | |- | ||
| + | |colspan="3"|⋱ | ||
| + | |- | ||
| + | |a<sub>ij</sub> | ||
| + | |… | ||
| + | |<sup>a<sub>mm</sub></sup>/<sub>2</sub> | ||
| + | |} | ||
| + | |} | ||
| + | * (E + ωR<sub>1</sub>)(E + ωR<sub>2</sub>)<sup>(x<sup>n+1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f, ω, τ > 0, n ∈ ℕ ∪ {0}, x<sup>0</sup> — задано | ||
| + | |||
| + | '''Теорема (о сходимости ПТИМ)'''. Пусть A = A* > 0, ω > <sup>τ</sup>/<sub>4</sub>. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении. | ||
| + | |||
| + | '''Доказательство.''' | ||
| + | * R<sub>1</sub> = R<sub>2</sub>* (так как A = A*) | ||
| + | * B = (E + ωR<sub>2</sub>*)(E + ωR<sub>2</sub>) = E + ω(R<sub>1</sub> + R<sub>2</sub>) + ω<sup>2</sup>R<sub>2</sub>*R<sub>2</sub> = E + ωA + ω<sup>2</sup>R<sub>2</sub>*R<sub>2</sub> | ||
| + | * (E − ωR<sub>2</sub>*)(E − ωR<sub>2</sub>) = E − ωA + ω<sup>2</sup>R<sub>2</sub>*R<sub>2</sub> | ||
| + | * B = (E − ωR<sub>2</sub>*)(E − ωR<sub>2</sub>) + 2ωA | ||
| + | * ((E − ωR<sub>2</sub>*)(E − ωR<sub>2</sub>)x, x) = ((E − ωR<sub>2</sub>*)x, (E − ωR<sub>2</sub>)x) ≥ 0 | ||
| + | * B ≥ 2ωA | ||
| + | * B − 2ωA ≥ 0 | ||
| + | |||
| + | так как ω > <sup>τ</sup>/<sub>4</sub>, то 2ω > 0,5τ | ||
| + | * B − 0,5τ > 0 | ||
| + | |||
| + | чтд | ||
| + | |||
| + | {{Численные Методы}} | ||
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 1. Численные методы линейной алгебры
[править] Параграф 6. Теоремы о сходимости итерационных методов
Следствие 4. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме.
Доказательство.
- метод Зейделя: (D + R1)(xn + 1 − xn)/τ + Axn = f
- B − 0,5τA > 0, τ = 1
- D + R1 = B, τ = 1
- D + R1 > 1/2 (R1 + D + R2)
- 2D + 2R1 > R1 + D + R2
- D + R1 − R2 > 0
- ((D + R1 − R2)x, x) > 0
- (Dx, x) + (R1x, x) − (R2x, x) > 0 ⇒ (Dx, x) > 0
- R1 = R2*
- R2 = R1*
- aii > 0, i = 1, m
- (R1x, x) = (x, R1*x) = (xR2, x) = (R2x, x)
чтд
[править] Параграф 7. Оценка скорости сходимости итерационных методов
- Ax = f (1)
- |A| ≠ 0, A ∈ ℝm × m
- B (xn + 1 − xn)/τ + Axn = f, n ∈ ℕ ∪ {0} (2)
- x0 задано
- vn = xn − x — погрешность
- B (vn + 1 − vn)/τ + Avn = 0, n ∈ ℕ ∪ {0} (3)
- v0 = x0 − x
Если в какой-либо норме удаётся получить оценку вида
- ||vn + 1|| ≤ ρ||vn||, 0 < ρ < 1 (4)
то ||vn|| ≤ ρn||v0|| → 0 при n → ∞
- ||xn − x|| ≤ ρn||x0 − x||
- ||xn − x|| ≤ ε||x0 − x||
- ρn ≤ ε
- 1/ε ≤ (1/ρ)n
- n ln 1/ρ ≥ ln 1/ε
- n ≥ n0(ε) = [ln 1/ε/ln 1/ρ]
ln 1/ρ — скорость сходимости итерационного метода
Пусть H — вещественное пространство, dim H = m
- ∀ x, y ∈ H (x, y) = ∑i = 1mxiyi
- ||x|| = (∑i = 1m xi2)1/2
Пусть B = B* > 0
Энергетическая норма ||x||B = (Bx,x)1/2
Теорема 4 (об оценке скорости сходимости итерационного метода). Пусть
- A = A* > 0
- B = B* > 0
- 0 < ρ < 1
- 1 − ρ/τB ≤ A ≤ 1 + ρ/τB (5)
Тогда итерационный метод (2) сходится к решению СЛАУ (1) и имеет место оценка ||vn + 1||B ≤ ρ||vn|| (6)
Доказательство. Сходимость:
- A ≤ 1 + ρ/τB
- A < 2/τB
- B − 0,5τA > 0
Оценки:
- B (vn + 1 − vn)/τ + Avn = 0 (*)
- ∃ B½, B−½, B½ = (B½)* > 0
умножим (*) на B−½ слева:
- B½ (vn + 1 − vn)/τ + B−½Avn = 0
- zn = B½vn
- vn = B−½zn
- zn + 1 − zn/τ + B−½AB−½zn = 0
- zn + 1 = zn & minus; τB−½AB−½zn = (E − τB−½AB−½)zn = Szn
- S = E − τB−½AB−½ (7)
- ||zn||2 = (zn, zn) = (B½vn, B½vn) = (Bvn, vn) = ||vn||B
Покажем, что S — самосопряжённая:
- S* = E − τB−½AB−½
Равенство Парсиваля
Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑k = 1mckek.
Тогда равенство Парсиваля есть ||x||2 = ∑k = 1mck2- Покажем, что все собственные значения матрицы S по модулю не превосходят ρ
- Пусть sk — собственное значение, k = 1, m
- (E − τB−½AB−½)x = skx, x ≠ 0
- Домножим на B½ слева:
- (B½ − τAB−½)x = skB½x
- y = B−½x
- x = B½)y
- (B − τA)y = skBy
- τAy = (1 − sk)By
- Ay = (1 − sk)/τBy
- Применим оценку (5):
- 1 − ρ/τ(By, y) ≤ (Ay, y) = (1 − sk)/τBy ≤ 1 + ρ/τ(By, y)
- (By, y) ≥ 0
- 1 − ρ ≤ 1 − sk ≤ 1 + ρ ⇒ |sk| < ρ, k = 1, m
- Пусть sk — собственное значение, k = 1, m
- S = S*
- {ek} — ортонормированный базис из собственных векторов S
- Sek = skek? k = 1, m
- zn = ∑k = 1mck(n)ek
- zn + 1 = Szn = ∑k = 1mskck(n)ek
- ||zn + 1||2 = ∑k = 1msk2(ck(n))2
- ||zn + 1||2 ≤ ρ2∑k = 1m(ck(n))2 = ρ2||zn||2
- ||zn + 1|| ≤ ρ||zn||
- ||vn + 1||B ≤ ρ||vn||B
чтд
Следствие 1.
- A = A* > 0
- B = B* > 0
- 0 < ρ < 1
- ∃ γ1 > 0, γ2 > 0: γ1B ≤ A ≤ γ2B (8)
Тогда
- τ = τ0 = 2/γ1 + γ2, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2
Доказательство:
- 1 − ρ/τ = γ1
- 1 + ρ/τ = γ2
- 2/τ = γ1 + γ2
- τ = 2/γ1 + γ2
- γ1 − γ2 = 2ρ/τ = ρ(γ1 + γ2)
- ρ = γ1 − γ2/γ1 + γ2 = 1 − γ1/γ2/1 + γ1/γ2 = 1 − ξ/1 + ξ
Следствие 2. Пусть A = a* > 0,
- γ1 = min1 ≤ k ≤ m λkA, > 0 в силу положительной определённости
- γ2 = max1 ≤ k ≤ m λkA
Тогда МПИ (xn+1 − xn)/τ + Axn = f, где τ = 2/γ1 + γ2, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2 — сходится, имеет место оценка ||xn − x|| ≤ ρ||xn − x||
Доказательство. аналогично Следствию 1.
[править] Параграф 8. Исследование сходимости ПТИМ
- Ax = f (1)
- |A| ≠ 0, A ∈ ℝm × m
- A = R1 + R2,
|
| ||||||||||||||||||||||
- (E + ωR1)(E + ωR2)(xn+1 − xn)/τ + Axn = f, ω, τ > 0, n ∈ ℕ ∪ {0}, x0 — задано
Теорема (о сходимости ПТИМ). Пусть A = A* > 0, ω > τ/4. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.
Доказательство.
- R1 = R2* (так как A = A*)
- B = (E + ωR2*)(E + ωR2) = E + ω(R1 + R2) + ω2R2*R2 = E + ωA + ω2R2*R2
- (E − ωR2*)(E − ωR2) = E − ωA + ω2R2*R2
- B = (E − ωR2*)(E − ωR2) + 2ωA
- ((E − ωR2*)(E − ωR2)x, x) = ((E − ωR2*)x, (E − ωR2)x) ≥ 0
- B ≥ 2ωA
- B − 2ωA ≥ 0
так как ω > τ/4, то 2ω > 0,5τ
- B − 0,5τ > 0
чтд
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Дополнительная информация |
Материалы к экзамену |
Эта статья является конспектом лекции.
