| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 05 лекция (от 27 февраля)|Предыдущая лекция]] | [[Численные Методы, 07 лекция (от 06 марта)|Следующая лекция]]
| + | == From Ebaums Inc to MurkLoar. == |
| - | | + | We at EbaumsWorld consider you as disgrace of human race. |
| - | = Глава 1 = | + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | | + | Dig yourself a grave - you will need it. |
| - | == Параграф 8. Исследование сходимости ПТИМ (продолжение) ==
| + | |
| - | | + | |
| - | Решаем систему (1), (2):
| + | |
| - | * 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. Пусть существуют такие две константы δ > 0, Δ > 0:
| + | |
| - | * A ≥ δE, R*<sub>2</sub>R<sub>2</sub> ≤ Δ/4 A (2)
| + | |
| - | * Положим ω = 2/√<span style="border-top:solid 1px">δΔ</span>, τ = 2/(γ<sub>1</sub> + γ<sub>2</sub>), γ<sub>1</sub> = √<span style="border-top:solid 1px">δ</span>/2 (√<span style="border-top:solid 1px">δΔ</span>/(√<span style="border-top:solid 1px">δ</span>+√<span style="border-top:solid 1px">Δ</span>)); γ<sub>2</sub> = √<span style="border-top:solid 1px">δΔ</span>/4 (4)
| + | |
| - | * ||x<sup>n + 1</sup> − x||<sub>B</sub> ≤ ρ ||x<sup>n</sup> − x||<sub>B</sub> (5)
| + | |
| - | * где B = (E + ωR*<sub>2</sub>)(E + ωR<sub>2</sub>), ρ = (1 − √<span style="border-top:solid 1px">η</span>)/(1 + 3√<span style="border-top:solid 1px">η</span>), η = δ/Δ (6)
| + | |
| - | ** R*<sub>2</sub> = R<sub>1</sub>
| + | |
| - | | + | |
| - | '''Доказательство'''. Для начала убедимся, что δ ≤ Δ. Лектор напомнит ещё, что значит неравенство (3):
| + | |
| - | * (Ax, x) ≥ δ(x, x) = δ||x||<sup>2</sup>, x ≠ 0
| + | |
| - | * (R*<sub>2</sub>R<sub>2</sub>x, x) = (R<sub>2</sub>x, R<sub>2</sub>x) = ||R<sub>2</sub>x||<sup>2</sup> ≤ Δ/4 (Ax, x)
| + | |
| - | * δ||x||<sup>2</sup> ≤ (Ax, x) = (Ax, x)<sup>2</sup>/(Ax, x)
| + | |
| - | Далее, что такое (Ax, x):
| + | |
| - | * (Ax, x) = ((R<sub>1</sub> + R<sub>2</sub>)x, x) = (R<sub>1</sub>x, x) + (R<sub>2</sub>x, x) = {так как R<sub>1</sub> = R*<sub>2</sub>} = (R*<sub>2</sub>x, x ) + (R<sub>2</sub>x, x) = (x, R<sub>2</sub>x) + (R<sub>2</sub>x, x) = 2(R<sub>2</sub>x, x)
| + | |
| - | Теперь можно записать, что
| + | |
| - | * δ||x||<sup>2</sup> ≤ (Ax, x) = (Ax, x)<sup>2</sup>/(Ax, x) = 4(R<sub>2</sub>x, x)<sup>2</sup>/(Ax, x)
| + | |
| - | Воспользуемся неравенством Коши-Буняковского:
| + | |
| - | * 4(R<sub>2</sub>x, x)<sup>2</sup>/(Ax, x) ≤ (4||R<sub>2</sub>x||<sup>2</sup>||x||<sup>2</sup>)/(Ax, x) ≤ 4Δ/4 (Ax, x)||x||<sup>2</sup>/(Ax, x) = Δ||x||<sup>2</sup>
| + | |
| - | Из этого следует, что δ ≤ Δ, причём неравенство почти всегда строгое.
| + | |
| - | | + | |
| - | Доказательство собственно теоремы:
| + | |
| - | | + | |
| - | //Где-то рядом записано: γ<sub>1</sub>B ≤ A ≤ γ<sub>2</sub>B
| + | |
| - | | + | |
| - | Запишем B = E + ωA + ω<sup>2</sup>R*<sub>2</sub>R<sub>2</sub> = (*)
| + | |
| - | * мы показали, что B ≥ 2ωA
| + | |
| - | * A ≤ ½ ωB
| + | |
| - | * γ<sub>2</sub> = 1/2ω
| + | |
| - | * (*) ≤ 1/δ A + ωA + ω<sup>2</sup> Δ/4 A = (1/δ + ω + ω<sup>2</sup>Δ/4)A
| + | |
| - | * γ<sub>1</sub> = (1/δ + ω + ω<sup>2</sup>Δ/4)<sup>−1</sup>
| + | |
| - | * ||x<sup>n + 1</sup> − x||<sub>B</sub> ≤ ρ ||x<sup>n</sup> − x||<sub>B</sub>
| + | |
| - | * ρ = (1 − ξ(ω))/(1 + 3ξ(ω)), ξ = γ<sub>1</sub>/γ<sub>2</sub>
| + | |
| - | * τ = 2/(γ<sub>1</sub>(ω)+γ<sub>2</sub>(ω))
| + | |
| - | * f(ω) = γ<sub>2</sub>(ω)/γ<sub>1</sub>(ω) = (1/δ + ω + ω<sup>2</sup>Δ/4)/(2ω) = ½ (1 + 1/δω + ωΔ/4)
| + | |
| - | * Для максимальной скорости сходимости необходимо найти минимум: f'(ω)=1/2 (Δ/4 − 1/δω<sup>2</sup>), 1/δω<sup>2</sup> = Δ/4, ω<sup>2</sup> = 4/δΔ, ω = 2/√<span style="border-top:solid 1px">δΔ</span> = ω<sub>0</sub>
| + | |
| - | * f''(ω<sub>0</sub>) = 1/δω<sup>3</sup> > 0 ⇒ ω<sub>0</sub> — минимум ⇒ максимальная скорость сходимости
| + | |
| - | | + | |
| - | Теперь получаем остальное:
| + | |
| - | * γ<sub>2</sub> = 1/2ω = √<span style="border-top:solid 1px">δΔ</span>/4
| + | |
| - | * γ<sub>1</sub> = (1/δ + 2/√<span style="border-top:solid 1px">δΔ</span> + 4Δ/(δΔ×4)) = 2(1/δ + 1/√<span style="border-top:solid 1px">δΔ</span>)<sup>−1</sup> = ½ ((√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>)/(δ√<span style="border-top:solid 1px">Δ</span>))<sup>−1</sup> = √<span style="border-top:solid 1px">δ</span>/2 (√<span style="border-top:solid 1px">δΔ</span>/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>))
| + | |
| - | * ρ = (1 − ξ)/(1 + ξ)
| + | |
| - | ** ξ = γ<sub>1</sub>/γ<sub>2</sub> = √<span style="border-top:solid 1px">δ</span>/2 (√<span style="border-top:solid 1px">δΔ</span> × 4/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>)√<span style="border-top:solid 1px">δΔ</span>) = 2√<span style="border-top:solid 1px">δ</span>/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>)
| + | |
| - | ** 1 − ξ = 1 − 2√<span style="border-top:solid 1px">δ</span>/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>) = (√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span> − 2√<span style="border-top:solid 1px">δ</span>)/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>) = (√<span style="border-top:solid 1px">Δ</span> − √<span style="border-top:solid 1px">δ</span>)/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>)
| + | |
| - | ** 1 + ξ = 1 + 2√<span style="border-top:solid 1px">δ</span>/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>) = (√<span style="border-top:solid 1px">Δ</span> − 3√<span style="border-top:solid 1px">δ</span>)/(√<span style="border-top:solid 1px">δ</span> + √<span style="border-top:solid 1px">Δ</span>)
| + | |
| - | ** ρ = (√<span style="border-top:solid 1px">Δ</span> − √<span style="border-top:solid 1px">δ</span>)/(√<span style="border-top:solid 1px">Δ</span> − 3√<span style="border-top:solid 1px">δ</span>) = (1 − √<span style="border-top:solid 1px">η</span>)/(1 + 3√<span style="border-top:solid 1px">η</span>), η = δ/Δ
| + | |
| - | | + | |
| - | чтд
| + | |
| - | | + | |
| - | Разные итерационные методы сравниваются по количеству действий для достижения необходимой точности:
| + | |
| - | * n<sub>0</sub>(ε) = [<sup>ln <sup>1</sup>/<sub>ε</sub></sup>/<sub>ln <sup>1</sup>/<sub>ρ</sub></sub>]
| + | |
| - | | + | |
| - | '''Замечание.''' Большинство задач, которое приходится решать математикам таково, что число η = O(m<sup>−2</sup>) маленькое, <sup>1</sup>/<sub>η</sub> ~ O(m<sup>2</sup>) большое. Посмотрим, сколько потребуется итераций:
| + | |
| - | * <sup>1</sup>/<sub>ρ</sub> = <sup>1 + 3√<span style="border-top:solid 1px">η</span></sup>/<sub>1 − √<span style="border-top:solid 1px">η</span></sub> ≈ <sup>(1 + 3√<span style="border-top:solid 1px">η</span>)(1 + √<span style="border-top:solid 1px">η</span>)</sup>/<sub>1 − η</sub> ≈ 1 + 4√<span style="border-top:solid 1px">η</span>. Тогда ln <sup>1</sup>/<sub>ρ</sub> = 4√<span style="border-top:solid 1px">η</span> = O(m<sup>−1</sup>), n<sub>0</sub>(ε) = O(m)
| + | |
| - | | + | |
| - | === Метод простой итерации ===
| + | |
| - | Теперь рассмотрим метод простой итерации (метод релаксации):
| + | |
| - | * ||x<sup>n + 1</sup> − x|| ≤ ρ ||x<sup>n</sup> − x||, ρ = <sup>1 − ξ</sup>/<sub>1 + ξ</sub>, ξ = <sup>γ<sub>1</sub></sup>/<sub>γ<sub>2</sub></sub>, ξ = η = O(m<sup>−2</sup>)
| + | |
| - | * 1/ρ = <sup>1 + η</sup>/<sub>1 − η</sub> ≈ (1 + η)<sup>2</sup> ≈ 1 + 2η
| + | |
| - | * ln <sup>1</sup>/<sub>ρ</sub> ≈ η, n<sub>0</sub>(ε) = O(m<sup>2</sup>)
| + | |
| - | | + | |
| - | == Параграф 9. Методы решения задач на собственные значения. ==
| + | |
| - | | + | |
| - | Это гигантский совершенно класс задач, очень сложный с точки зрения решения.
| + | |
| - | | + | |
| - | Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)
| + | |
| - | * λ — собственные значения
| + | |
| - | * x — собственные вектора
| + | |
| - | | + | |
| - | '''Замечание.''' Математики перенормировывают собственные вектора каждый раз. Чтобы ошибки округления не исказили сам подход.
| + | |
| - | | + | |
| - | Находим корни характеристического многочлена f(λ) = |A − λE| = 0
| + | |
| - | | + | |
| - | Два круга проблем:
| + | |
| - | * Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
| + | |
| - | * Полная проблема собственных значений — нужно находить все собственные значения
| + | |
| - | | + | |
| - | Всего m значений (с учётом кратности): λ<sub>k</sub>, k = 1..m
| + | |
| - | | + | |
| - | Вообще говоря, собственные значения комплексные.
| + | |
| - | | + | |
| - | Все методы итерационные. Один из самых простых методов — степенной метод.
| + | |
| - | | + | |
| - | === Степенной метод ===
| + | |
| - | x<sub>n</sub> — n-я итерация.
| + | |
| - | | + | |
| - | Степенной метод — метод, который описывается уравнением 2:
| + | |
| - | * x<sub>n + 1</sub> = Ax<sub>n</sub> (2)
| + | |
| - | * n = 0, 1, ..., x<sub>0</sub> — начальное приближение
| + | |
| - | * x<sub>n</sub> = A<sup>n</sup>x<sub>0</sub> (3)
| + | |
| - | | + | |
| - | Условия:
| + | |
| - | * Предположения относительно матрицы A:
| + | |
| - | ** Все собственные значения расположены в порядке неубывания модуля: |λ<sub>1</sub>| ≤ |λ<sub>2</sub>| ≤ |λ<sub>3</sub>| ≤ ... ≤ |λ<sub>m − 1</sub>| < |λ<sub>m</sub>|
| + | |
| - | ** Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e<sub>k</sub>}<sub>1</sub><sup>m</sup> — базис из собственных векторов A (Ae<sub>k</sub> = λ<sub>k</sub>e<sub>k</sub>, k = 1..m)
| + | |
| - | ** Ограничение B: последнее собственное значение не является кратным: |(λ<sub>m − 1</sub>)/(λ<sub>m</sub>) < 1
| + | |
| - | ** Ограничение C: ∀ x = c<sub>1</sub>e<sub>1</sub> + ... + c<sub>m</sub>e<sub>m</sub>, c<sub>m</sub> ≠ 0
| + | |
| - | | + | |
| - | x<sub>n</sub> = c<sub>1</sub>λ<sub>1</sub><sup>n</sup>e<sub>1</sub> + c<sub>2</sub>λ<sub>2</sub><sup>n</sup>e<sub>2</sub> + ... + c<sub>m</sub>λ<sub>m</sub><sup>n</sup>e<sub>m</sub>
| + | |
| - | | + | |
| - | x<sub>n</sub>/c<sub>m</sub>λ<sup>n</sup><sub>m</sub> = (c<sub>1</sub>/c<sub>m</sub>)(λ<sub>1</sub>/λ<sub>m</sub>)<sup>n</sup>e<sub>1</sub> + (c<sub>2</sub>/c<sub>m</sub>)(λ<sub>2</sub>/λ<sub>m</sub>)<sup>n</sup>e<sub>2</sub> + ... + e<sub>m</sub>
| + | |
| - | | + | |
| - | x<sub>n</sub><sup>(i) — координата</sup> = c<sub>1</sub>λ<sub>1</sub><sup>n</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>λ<sub>2</sub><sup>n</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>λ<sub>m</sub><sup>n</sup>e<sub>m</sub><sup>(i)</sup>
| + | |
| - | x<sub>n+1</sub><sup>(i)</sup> = c<sub>1</sub>λ<sub>1</sub><sup>n+1</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>λ<sub>2</sub><sup>n+1</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>λ<sub>m</sub><sup>n+1</sup>e<sub>m</sub><sup>(i)</sup>
| + | |
| - | | + | |
| - | x<sub>n+1</sub><sup>(i)</sup>/x<sub>n</sub><sup>(i)</sup> = λ<sub>m</sub><sup>(n)</sup> = λ<sub>m</sub> + O(|λ<sub>m − 1</sub>/λ<sub>m</sub>|)<sup>n</sup>
| + | |
| - | | + | |
| - | {{Численные Методы}}
| + | |
| - | {{Lection-stub}}
| + | |
