Текущая версия |
Ваш текст |
Строка 1: |
Строка 1: |
- | = Глава 1 = | + | == From Ebaums Inc to MurkLoar. == |
- | == Система линейных алгебраических уравнений (СЛАУ) ==
| + | We at EbaumsWorld consider you as disgrace of human race. |
- | '''Система линейных алгебраических уравнений:'''
| + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
- | * Ax = f
| + | Dig yourself a grave - you will need it. |
- | * A (m × m), det A ≠ 0 — решение есть, оно единственное
| + | |
- | * x = (x<sub>1</sub>, x<sub>2</sub>, ... x<sub>m</sub>)<sup>T</sup>
| + | |
- | * f = (f<sub>1</sub>, f<sub>2</sub>, ... f<sub>m</sub>)<sup>T</sup>
| + | |
- | | + | |
- | == Группы методов решения СЛАУ ==
| + | |
- | К курсе рассматриваются две группы методов:
| + | |
- | # Прямые (точные) методы
| + | |
- | # Итерационные (приближённые) методы
| + | |
- | | + | |
- | == Прямой метод решения СЛАУ ==
| + | |
- | '''Прямой метод решения СЛАУ''' — метод, который позволяет реализовать в алгоритме определённые формулы, то есть аналитическое решение.
| + | |
- | | + | |
- | == Задача на собственные значения ==
| + | |
- | '''Задача на собственные значения''' — задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение.
| + | |
- | | + | |
- | == Факторизация матрицы ==
| + | |
- | '''Факторизация матрицы''' — представление матрицы А в виде произведения B × C, где
| + | |
- | {|
| + | |
- | |B — нижнетреугольная матрица:
| + | |
- | {|style="text-align:center"
| + | |
- | |b<sub>11</sub>
| + | |
- | |0
| + | |
- | |0
| + | |
- | |...
| + | |
- | |0
| + | |
- | |-
| + | |
- | |b<sub>21</sub>
| + | |
- | |b<sub>22</sub>
| + | |
- | |0
| + | |
- | |...
| + | |
- | |0
| + | |
- | |-
| + | |
- | |colspan="5"|...
| + | |
- | |-
| + | |
- | |b<sub>1m</sub>
| + | |
- | |b<sub>2m</sub>
| + | |
- | |b<sub>3m</sub>
| + | |
- | |...
| + | |
- | |b<sub>mm</sub>
| + | |
- | |}
| + | |
- | |C — верхнетреугольная матрица с единицами на диаонали:
| + | |
- | {|style="text-align:center"
| + | |
- | |1
| + | |
- | |c<sub>12</sub>
| + | |
- | |c<sub>13</sub>
| + | |
- | |...
| + | |
- | |c<sub>1m</sub>
| + | |
- | |-
| + | |
- | |0
| + | |
- | |1
| + | |
- | |c<sub>23</sub>
| + | |
- | |...
| + | |
- | |c<sub>2m</sub>
| + | |
- | |-
| + | |
- | |colspan="5"|...
| + | |
- | |-
| + | |
- | |0
| + | |
- | |0
| + | |
- | |0
| + | |
- | |...
| + | |
- | |1
| + | |
- | |}
| + | |
- | |}
| + | |
- | | + | |
- | == В каком порядке ищутся элементы матриц B и C при факторизации А = B × C ==
| + | |
- | Процесс нахождения матриц B и C размерами m × m разбивается на m этапов, причём на каждом этапе сначала по формуле b<sub>ij</sub> = a<sub>ij</sub> − Σ<sub>l=1</sub><sup>j−1</sup> b<sub>il</sub>×c<sub>lj</sub> находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.
| + | |
- | | + | |
- | == Условие существования и единственности разложения А = B × C ==
| + | |
- | Все главные угловые миноры A отличны от 0:
| + | |
- | {|
| + | |
- | |A<sub>1</sub> = a<sub>11</sub> ≠ 0
| + | |
- | |;
| + | |
- | |
| + | |
- | {|style="text-align:center"
| + | |
- | |rowspan="2"|A<sub>2</sub> = (
| + | |
- | |a<sub>11</sub>
| + | |
- | |a<sub>12</sub>
| + | |
- | |rowspan="2"|) ≠ 0
| + | |
- | |-
| + | |
- | |a<sub>21</sub>
| + | |
- | |a<sub>22</sub>
| + | |
- | |}
| + | |
- | |;
| + | |
- | |…;
| + | |
- | |
| + | |
- | {|style="text-align:center"
| + | |
- | |rowspan="3"|A<sub>i</sub> = (
| + | |
- | |a<sub>11</sub>
| + | |
- | |...
| + | |
- | |a<sub>1i</sub>
| + | |
- | |rowspan="3"|) ≠ 0
| + | |
- | |-
| + | |
- | |colspan="3"|...
| + | |
- | |-
| + | |
- | |a<sub>i1</sub>
| + | |
- | |...
| + | |
- | |a<sub>ii</sub>
| + | |
- | |}
| + | |
- | |}
| + | |
- | | + | |
- | == Связь метода Гаусса с разложением A = B × C ==
| + | |
- | Три этапа метода Гаусса соответствуют трём этапам факторизации:
| + | |
- | * В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> операций — то же количество действий требуется для нахождения матриц B и C
| + | |
- | * Для решения уравнения By = f требуется <sup>m(m + 1)</sup>/<sub>2</sub> действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
| + | |
- | * Для решения уравнения Cx = y требуется <sup>m(m − 1)</sup>/<sub>2</sub> действий — в точности то число действий, которое требуется для обратного хода Гаусса
| + | |
- | | + | |
- | == Метод Гаусса-Жордана ==
| + | |
- | '''Метод Гаусса-Жордана''':
| + | |
- | * Обозначим A<sup>−1</sup> = X. Тогда AX = E
| + | |
- | * Запишем в явном виде:
| + | |
- | * ∑<sub>l = 1</sub><sup>m</sup>a<sub>il</sub>x<sub>lj</sub> = δ<sub>ij</sub>, i, j = 1..m
| + | |
- | * m<sup>2</sup> неизвестных, поэтому действий m<sup>6</sup>
| + | |
- | * Разумно организовав алгоритм, можно получить порядка m<sup>3</sup> действий
| + | |
- | | + | |
- | == Метод квадратного корня (метод Холецкого) ==
| + | |
- | * Решаем уравнение Ax = f
| + | |
- | * |A| ≠ 0 (m × m)
| + | |
- | * A = A* ⇔ a<sub>ij</sub> = <span style="border-top:solid 1px">a<sub>ji</sub></span>
| + | |
- | * A = A<sup>T</sup> — для вещественных матриц
| + | |
- | | + | |
- | Факторизуем матрицу A в виде A = S*DS
| + | |
- | {|style="text-align:center"
| + | |
- | |
| + | |
- | |s<sub>11</sub>
| + | |
- | |s<sub>12</sub>
| + | |
- | |s<sub>13</sub>
| + | |
- | |...
| + | |
- | |s<sub>1m</sub>
| + | |
- | |-
| + | |
- | |
| + | |
- | |0
| + | |
- | |s<sub>22</sub>
| + | |
- | |s<sub>23</sub>
| + | |
- | |...
| + | |
- | |s<sub>2m</sub>
| + | |
- | |-
| + | |
- | |S =
| + | |
- | |0
| + | |
- | |0
| + | |
- | |s<sub>33</sub>
| + | |
- | |..
| + | |
- | |s<sub>3m</sub>
| + | |
- | |-
| + | |
- | |
| + | |
- | |colspan="5"|...
| + | |
- | |-
| + | |
- | |
| + | |
- | |0
| + | |
- | |0
| + | |
- | |0
| + | |
- | |...
| + | |
- | |s<sub>mm</sub>
| + | |
- | |}
| + | |
- | s<sub>ii</sub> > 0, i = <span style="border-top:solid 1px">2…m</span>
| + | |
- | | + | |
- | D = diag (d<sub>11</sub>, …, d<sub>mm</sub>) d<sub>ii</sub> = ±1, i = 1..m
| + | |
- | | + | |
- | Тогда система решается следующим образом:
| + | |
- | * S*DSx = f
| + | |
- | * S*Dy = f
| + | |
- | * Sx = y
| + | |
- | Эти две системы решаются явным образом, ибо матрицы треугольные.
| + | |
- | | + | |
- | == Достоинства и недостатки метода квадратного корня ==
| + | |
- | Плюс:
| + | |
- | * Количество действий сокращается в два раза (<sup>m<sup>3</sup></sup>/<sub>6</sub> умножений и делений + m извлечений корня)
| + | |
- | Минусы:
| + | |
- | * Только для эрмитовых матриц
| + | |
- | | + | |
- | == Что значит «решить СЛАУ итерационным методом» ==
| + | |
- | * x<sub>i</sub><sup>n</sup> — i-я кордината, n-я итерация
| + | |
- | * x<sup>0</sup> — начальное приближение
| + | |
- | | + | |
- | Далее организуется процесс так, что lim<sub>n → ∞</sub>x<sup>n</sup> → x, то есть, в некоторой норме |x<sup>n</sup> − x| < ε, ε > 0
| + | |
- | | + | |
- | == Вопросы, рассматриваемые при исследовании итерационного метода ==
| + | |
- | * Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
| + | |
- | * С какой скоростью
| + | |
- | | + | |
- | == Метод Якоби ==
| + | |
- | * x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> − ∑<sub>j = 1</sub><sup>i − 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup> − ∑<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n ∈ ℕ ∪ {0}
| + | |
- | * x<sup>0</sup> — задано
| + | |
- | | + | |
- | == Достоинства и недостатки метода Якоби ==
| + | |
- | Плюс:
| + | |
- | * Данный метод реализуется достаточно просто
| + | |
- | Минус:
| + | |
- | * Очень медленная сходимость
| + | |
- | | + | |
- | == Метод Зейделя ==
| + | |
- | * x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> − ∑<sub>j = 1</sub><sup>i − 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n + 1</sup> − ∑<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n ∈ ℕ ∪ {0} (3)
| + | |
- | * x<sup>0</sup> — задано
| + | |
- | | + | |
- | == Соотношение сложностей методов Якоби и Зейделя ==
| + | |
- | По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации
| + | |
- | | + | |
- | == Двуслойная запись ==
| + | |
- | '''Двуслойная запись''' — когда связываются две соседние итерации.
| + | |
- | | + | |
- | == Каноническая форма записи двуслойного итерационного метода решения СЛАУ ==
| + | |
- | '''Определение'''. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m × m), det A ≠ 0 называется его запись в виде:
| + | |
- | * B<sub>n + 1</sub> <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ<sub>n + 1</sub></sub> + Ax<sup>n</sup> = f (4)
| + | |
- | где
| + | |
- | * τ<sub>n + 1</sub> > 0, n ∈ ℕ ∪ {0}
| + | |
- | * x<sup>0</sup> — задано
| + | |
- | * ∃B<sub>n + 1</sub><sup>−1</sup>
| + | |
- | | + | |
- | == Виды итерационных методов ==
| + | |
- | * Метод явный, если B<sub>n + 1</sub> = E. Если матрица диагональная, то тоже явный.
| + | |
- | * Метод стационарный, если
| + | |
- | ** B<sub>n + 1</sub> = B
| + | |
- | ** τ<sub>n + 1</sub> = τ
| + | |
- | | + | |
- | == Метод простой итерации ==
| + | |
- | '''Метод простой итерации (МПИ)''':
| + | |
- | * (МПИ) (x<sup>n+1</sup> − x<sup>n</sup>)/τ + Ax<sup>n</sup> = f, x<sup>0</sup> — задано, n ∈ ℕ ∪ {0}, τ > 0
| + | |
- | * Если τ меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.
| + | |
- | | + | |
- | == Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ) ==
| + | |
- | * A = R<sub>1</sub> + R<sub>2</sub>, где R<sub>1</sub> — нижнетреугольная матрица с диагональными элементам r<sub>1<sub>ii</sub></sub> = a<sub>ii</sub>/2, R<sub>2</sub> — верхнетреугольная матрица с диагональными элементам r<sub>2<sub>ii</sub></sub> = a<sub>ii</sub>/2.
| + | |
- | * (E + ωR<sub>1</sub>)(E + ωR<sub>2</sub>)((x<sup>n + 1</sup> − x<sup>n</sup>)/τ) + Ax<sup>n</sup> = f (5)
| + | |
- | ** n ∈ ℕ ∪ {0}, x<sup>0</sup> задано, ω > 0, τ > 0
| + | |
- | * Применительно к канонической записи B = (E + ωR<sub>1</sub>)(E + ωR<sub>2</sub>)
| + | |
- | | + | |
- | == Невязка ==
| + | |
- | r<sup>n</sup> = f − Ax<sup>n</sup>
| + | |
- | | + | |
- | == Энергетическая норма ==
| + | |
- | '''Энергетическая норма''' ||x||<sub>D</sub> = (Dx,x)<sup><sup>1</sup>/<sub>2</sub></sup>, где D — положительно определённый опрератор, то есть (Dx, x) > 0, ∀ x ≠ 0.
| + | |
- | | + | |
- | == Вектор погрешности ==
| + | |
- | '''Вектор погрешности''': v<sup>n</sup> = x<sup>n</sup> − x.
| + | |
- | | + | |
- | == Матрица перехода ==
| + | |
- | '''S = E − τB<sup>−1</sup>A'''
| + | |
- | | + | |
- | Вывод:
| + | |
- | * Ax = f
| + | |
- | * ∃ A<sup>−1</sup> (m × m)
| + | |
- | * B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f
| + | |
- | * x<sup>n</sup> = v<sup>n</sup> + x
| + | |
- | * B (v<sup>n + 1</sup> − v<sup>n</sup>)/τ + Av<sup>n</sup> = 0
| + | |
- | * (v<sup>n + 1</sup> − v<sup>n</sup>)/τ + B<sup>−1</sup>Av<sup>n</sup> = 0
| + | |
- | * v<sup>n+1</sup> = v<sup>n</sup> − τB<sup>−1</sup>Av<sup>n</sup> = (E − τB<sup>−1</sup>A)v<sup>n</sup>
| + | |
- | * S = E − τB<sup>−1</sup>A
| + | |
- | | + | |
- | == Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода ==
| + | |
- | '''Теорема 1'''. Итерационный метод B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E − τB<sup>−1</sup>A по модулю меньше 1: |λ<sub>k</sub><sup>S</sup>| < 1.
| + | |
- | | + | |
- | Это означает, что оператор S — сжимающий.
| + | |
- | | + | |
- | == Достаточное условие сходимости итерационного метода (теорема Самарского) ==
| + | |
- | '''Теорема (Самарского, о достаточном условии сходимости метода B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f)'''. Пусть есть A = A* = A<sup>T</sup> > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||x<sup>n</sup> − x|| = (∑<sub>i = 1</sub><sup>m</sup> (x<sub>i</sub><sup>n</sup> − xi)<sup>2</sup>)<sup><sup>1</sup>/<sub>2</sub></sup> → 0, n → ∞.
| + | |
- | | + | |
- | == Теорема о сходимости метода Якоби ==
| + | |
- | '''Следствие 1 теоремы Самарского'''. Пусть ∃ A = A* > 0, 2D > A. Тогда Методя Якоби сходится при любом начальном приближении.
| + | |
- | | + | |
- | == Теорема о сходимости метода простой итерации ==
| + | |
- | '''Следствие 3 теоремы Самарского'''. Пусть ∃ A = A* > 0, γ<sub>2</sub> = max<sub>1 ≤ x ≤ m</sub>λ<sub>k</sub><sup>A</sup> > 0. Тогда 0 < τ < 2/γ<sub>2</sub> МПИ сходится при ∀ x<sup>0</sup>
| + | |
- | | + | |
- | == Теорема о сходимости метода Зейделя ==
| + | |
- | '''Следствие 4'''. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме.
| + | |
- | Вообще достаточно только самосопряженности оператора А: A = A* > 0
| + | |
- | | + | |
- | == Скорость сходимости итерационного метода ==
| + | |
- | ln <sup>1</sup>/<sub>ρ</sub> — '''скорость сходимости итерационного метода'''
| + | |
- | | + | |
- | == Оценка скорости сходимости итерационного метода ==
| + | |
- | '''Теорема (об оценке скорости сходимости итерационного метода)'''. Пусть
| + | |
- | * A = A* > 0
| + | |
- | * B = B* > 0
| + | |
- | * 0 < ρ < 1
| + | |
- | * <sup>1 − ρ</sup>/<sub>τ</sub>B ≤ A ≤ <sup>1 + ρ</sup>/<sub>τ</sub>B
| + | |
- | Тогда итерационный метод B <sup>(x<sup>n + 1</sup> − x<sup>n</sup>)</sup>/<sub>τ</sub> + Ax<sup>n</sup> = f сходится к решению СЛАУ Ax = f и имеет место оценка ||v<sup>n + 1</sup>||<sub>B</sub> ≤ ρ||v<sup>n</sup>||
| + | |
- | | + | |
- | == Равенство Парсеваля ==
| + | |
- | '''Равенство Парсеваля'''
| + | |
- | Пусть 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>
| + | |
- | | + | |
- | == Оценка скорости сходимости МПИ ==
| + | |
- | '''Следствие 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+1</sup> − x|| ≤ ρ||x<sup>n</sup> − x||
| + | |
- | | + | |
- | == Теорема о сходимости ПТИМ ==
| + | |
- | '''Теорема (о сходимости ПТИМ)'''. Пусть A = A* > 0, ω > <sup>τ</sup>/<sub>4</sub>. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.
| + | |
- | | + | |
- | == Теорема об оценке скорости сходимости ПТИМ ==
| + | |
- | '''Теорема (об оценке скорости сходимости ПТИМ)'''. Пусть A = A* > 0. Пусть существуют такие две константы δ > 0, Δ > 0:
| + | |
- | * A ≥ δE, R<sub>2</sub>*R<sub>2</sub> ≤ <sup>Δ</sup>/<sub>4</sub> A (2)
| + | |
- | * Положим ω = <sup>2</sup>/<sub>√<span style="border-top:solid 1px">δΔ</span></sub>, τ = <sup>2</sup>/<sub>γ<sub>1</sub> + γ<sub>2</sub></sub>, γ<sub>1</sub> = <sup>√<span style="border-top:solid 1px">δ</span></sup>/<sub>2</sub> (<sup>√<span style="border-top:solid 1px">δΔ</span></sup>/<sub>√<span style="border-top:solid 1px">δ</span>+√<span style="border-top:solid 1px">Δ</span></sub>); γ<sub>2</sub> = <sup>√<span style="border-top:solid 1px">δΔ</span></sup>/<sub>4</sub>
| + | |
- | * ||x<sup>n + 1</sup> − x||<sub>B</sub> ≤ ρ ||x<sup>n</sup> − x||<sub>B</sub>
| + | |
- | * где B = (E + ωR<sub>2</sub>*)(E + ωR<sub>2</sub>), ρ = <sup>1 − √<span style="border-top:solid 1px">η</span></sup>/<sub>1 + 3√<span style="border-top:solid 1px">η</span></sub>, η = <sup>δ</sup>/<sub>Δ</sub>
| + | |
- | ** R<sub>2</sub>* = R<sub>1</sub>
| + | |
- | | + | |
- | == Оценка скорости сходимости для метода простой итерации ==
| + | |
- | * ||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>)
| + | |
- | | + | |
- | == Задача на собственные значения ==
| + | |
- | Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)
| + | |
- | * λ — собственные значения
| + | |
- | * x — собственные вектора
| + | |
- | | + | |
- | Два круга проблем:
| + | |
- | * Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
| + | |
- | * Полная проблема собственных значений — нужно находить все собственные значения
| + | |
- | | + | |
- | Всего m значений (с учётом кратности): λ<sub>k</sub>, k = 1..m
| + | |
- | | + | |
- | Вообще говоря, собственные значения комплексные.
| + | |
- | | + | |
- | Все методы итерационные. Один из самых простых методов — степенной метод.
| + | |
- | | + | |
- | == Степенной метод нахождения собственных значений ==
| + | |
- | '''Степенной метод''' — метод, который описывается уравнением 1:
| + | |
- | * x<sub>n + 1</sub> = Ax<sub>n</sub> (1)
| + | |
- | * n = 0, 1, ..., x<sub>0</sub> — начальное приближение
| + | |
- | * x<sub>n</sub> = A<sub>n</sub>x<sub>0</sub>
| + | |
- | | + | |
- | == Условия для степенного метода ==
| + | |
- | * Предположения относительно матрицы A:
| + | |
- | ** Все собственные значения расположены в порядке неубывания модуля: |λ<sub>1</sub>| ≤ |λ<sub>2</sub>| ≤ |λ<sub>3</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
| + | |
- | | + | |
- | == Метод обратных итераций ==
| + | |
- | # ∃ A<sup>−1</sup>. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
| + | |
- | #* Ax<sub>n + 1</sub> = x<sub>n</sub>, n = 0, 1, …, x<sub>0</sub> — начальное приближение (3) Этот метод неявный. Перепишем его как:
| + | |
- | #* x<sub>n + 1</sub> = A<sup>−1</sup>x<sub>n</sub> (4)
| + | |
- | #* x<sub>n</sub> = (A<sup>−1</sup>)<sup>n</sup>x<sub>n</sub>
| + | |
- | | + | |
- | Условия:<br />
| + | |
- | A) ∃ {e<sub>k</sub>}<sub>1</sub><sup>m</sup> из СВ<br />
| + | |
- | B) |λ<sub>1</sub>/λ<sub>2</sub>| < 1<br />
| + | |
- | C) x<sub>0</sub> = c<sub>1</sub>e<sub>1</sub>+ … + c<sub>m</sub>e<sub>m</sub>, c<sub>1</sub> ≠ 0
| + | |
- | | + | |
- | Тогда:
| + | |
- | * x<sub>n</sub> = c<sub>1</sub>λ<sub>1</sub><sup>−n</sup>e<sub>1</sub>+ … + c<sub>m</sub>λ<sub>m</sub><sup>−n</sup>e<sub>m</sub>
| + | |
- | * x<sub>n</sub>/e<sub>1</sub>λ<sub>1</sub><sup>−n</sup> = e<sub>1</sub> + … + (c<sub>m</sub>/c<sub>1</sub>)(λ<sub>1</sub>/λ<sub>m</sub>)<sup>n</sup>e<sub>m</sub>
| + | |
- | | + | |
- | == Метод обратных итераций со сдвигом ==
| + | |
- | * (A − αE)x<sub>n + 1</sub> = x<sub>n</sub> (5)
| + | |
- | ** n = 0, 1, …, x<sub>0</sub> — начальное приближение, α ∈ R
| + | |
- | * ∃ (A − αE)<sup>−1</sup>
| + | |
- | * x<sub>n + 1</sub> = (A − αE)<sup>−1</sup>x<sub>n</sub>
| + | |
- | * x<sub>n</sub> = e<sub>l</sub>
| + | |
- | * 1/|λ<sub>l</sub> − α| = max<sub>1 ≤ k ≤ m</sub> 1/|λ<sub>k</sub> − α|
| + | |
- | | + | |
- | == Что такое верхняя почти треугольная форма ==
| + | |
- | Верхняя почти треугольная форма — форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.
| + | |
- | | + | |
- | == Преобразование элементарных отражений (преобразование Хаусхолдера) ==
| + | |
- | '''Определение'''. Преобразование элементарных отражений (Преобразование Хаусхолдера).
| + | |
- | Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vv<sup>T</sup>/||v||<sup>2</sup>
| + | |
- | | + | |
- | == QR-алгоритм решения полной проблемы собственных значений ==
| + | |
- | | + | |
- | ∀ A = Q × R, Q<sup>−1</sup> = Q<sup>T</sup>, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.
| + | |
- | | + | |
- | == Количество действий для работы QR-алгоритма ==
| + | |
- | * полная — O(m<sup>3</sup>)
| + | |
- | * ВПТФ — O(m<sup>2</sup>)
| + | |
- | * А - трехдиагональная - O(m)
| + | |
- | | + | |
- | == Теорема о сохранении ВПТФ ==
| + | |
- | Пусть C = B × A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.
| + | |
- | | + | |
- | = Глава 2 =
| + | |
- | == Задача интерполяции ==
| + | |
- | Суть задачи: есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x<sub>0</sub> < x<sub>1</sub> < x<sub>2</sub> < … < x<sub>n</sub> ≤ b — {x<sub>i</sub>}<sub>0</sub><sup>n</sup> — узлы интерполирование (n + 1 штук). Есть f(x<sub>i</sub>) = f<sub>i</sub>, i = 0…n. Если полином P<sub>n</sub>(x) = a<sub>0</sub> + a<sub>1</sub>x + … a<sub>n</sub>x<sup>n</sup> такой, что P<sub>n</sub>(x<sub>i</sub>) = f(x<sub>i</sub>), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).
| + | |
- | | + | |
- | == Интерполяционный полином ==
| + | |
- | Если полином P<sub>n</sub>(x) = a<sub>0</sub> + a<sub>1</sub>x + … a<sub>n</sub>x<sup>n</sup> такой, что P<sub>n</sub>(x<sub>i</sub>) = f(x<sub>i</sub>), i = 0…n (1), то данный полином называется '''интерполяционным''' для f (интерполирует f).
| + | |
- | | + | |
- | == Существование и единственность интерполяционного полинома ==
| + | |
- | При условиях, накладываемых в постановке задачи интерполяции (узлы интерполирования не совпадают) интерполяционный полином существует и единственный.
| + | |
- | | + | |
- | == Интерполяционный полином в форме Лагранжа ==
| + | |
- | L<sub>n</sub>(x) = ∑<sub>k = 0</sub><sup>n</sup>(ω(x))/((x −x<sub>k</sub>)ω'(x<sub>k</sub>)) × f(x<sub>k</sub>), где
| + | |
- | * ω(x) = (x − x<sub>0</sub>)(x − x<sub>1</sub>)…(x − x<sub>n</sub>) = ∏<sub>i = 0</sub><sup>n</sup>(x<sub>i</sub> − x<sub>j</sub>)
| + | |
- | * ω(x) = [ ](x − x<sub>k</sub>)
| + | |
- | * ω'(x) = [ ] + [ ]'(x − x<sub>k</sub>)
| + | |
- | * ω'(x<sub>k</sub>) = ∏<sub>k ≠ j</sub><sup>n</sup>(x<sub>k</sub> − x<sub>j</sub>)
| + | |
- | | + | |
- | == Определение погрешности интерполяционного полинома ==
| + | |
- | Погрешность интерполяционной формулы Лагранжа ψ<sub>L<sub>n</sub></sub>(x) = f(x) − L<sub>n</sub>(x). Во всех узлах она будет совпадать: ψ<sub>L<sub>n</sub></sub>(x<sub>i</sub>) = 0.
| + | |
- | | + | |
- | '''Замечание 1'''. Если f(x) — полином степени ≤ n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.
| + | |
- | | + | |
- | '''Замечание 2'''. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.
| + | |
- | | + | |
- | == Разделённая разность ==
| + | |
- | | + | |
- | '''Разделённой разностью первого порядка''', построенной по узлам x<sub>i</sub>, x<sub>j</sub> называется отношение f(x<sub>i</sub>, x<sub>j</sub>) = (f(x<sub>j</sub>) − f(x<sub>i</sub>)/(x<sub>j</sub> − x<sub>i</sub>))
| + | |
- | | + | |
- | '''Разделённая разность k+1-го порядка''': пусть есть f(x<sub>j</sub>, x<sub>j + 1</sub>, …, x<sub>j + k</sub>), f(x<sub>j + 1</sub>, x<sub>j + 2</sub>, …, x<sub>j + k + 1</sub>) — разности k-го порядка. Тогда f(x<sub>j</sub>, x<sub>j + 1</sub>, …, x<sub>j + k + 1</sub>) = (f(x<sub>j + 1</sub>, x<sub>j + 2</sub>, …, x<sub>j + k + 1</sub>) − f(x<sub>j</sub>, x<sub>j + 1</sub>, …, x<sub>j + k</sub>))/(x<sub>j + k + 1</sub> − x<sub>j</sub>) — разделённая разность k + 1-го порядка.
| + | |
- | | + | |
- | == Выражение разделённой разности через значения функции в точках ==
| + | |
- | Разделённая разность k-го порядка, построенная по узлам x<sub>0</sub>, … x<sub>k</sub> может быть записана как f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>k</sub>) = ∑<sub>i = 0</sub><sup>k</sup>(f(x<sub>i</sub>))/(ω<sub>0, k</sub>'(x<sub>i</sub>))
| + | |
- | | + | |
- | == Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка ==
| + | |
- | f(x<sub>k</sub>) = f(x<sub>0</sub>) + (x<sub>k</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x<sub>k</sub> − x<sub>0</sub>)(x<sub>k</sub> − x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + … + (x<sub>k</sub> − x<sub>0</sub>)(x<sub>k</sub> − x<sub>1</sub>)…(x<sub>k</sub> − x<sub>k − 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>k</sub>)
| + | |
- | | + | |
- | == Интерполяционная функция в форме Ньютона ==
| + | |
- | N<sub>n</sub>(x) = f(x<sub>0</sub>) + (x − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x − x<sub>0</sub>)(x − x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + … + (x − x<sub>0</sub>)(x − x<sub>1</sub>)…(x − x<sub>n − 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>n</sub>)
| + | |
- | | + | |
- | == Погрешность интерполяционной формулы Ньютона ==
| + | |
- | Погрешность та же самая, но записана внешне по-другому:
| + | |
- | | + | |
- | |ψ<sub>N<sub>n</sub></sub>(x)| = |f(x) − N<sub>n</sub>(x)| ≤ M<sub>n + 1</sub>/(n + 1)! × |ω(x)|, M<sub>n + 1</sub> = sup<sub>a ≤ x≤ b</sub> |f(x)<sup>(n + 1)</sup>|
| + | |
- | | + | |
- | == Когда лучше использовать Ньютона, а когда — Лагранжа
| + | |
- | * Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
| + | |
- | * Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах
| + | |
- | | + | |
- | == Интерполяционная формула Эрмита ==
| + | |
- | Пусть у нас есть узлы x<sub>0</sub>, … x<sub>m</sub> — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:
| + | |
- | {|
| + | |
- | |x<sub>0</sub>
| + | |
- | |x<sub>1</sub>
| + | |
- | |…
| + | |
- | |x<sub>m</sub>
| + | |
- | |-
| + | |
- | |f(x<sub>0</sub>)
| + | |
- | |f(x<sub>1</sub>)
| + | |
- | |…
| + | |
- | |f(x<sub>m</sub>)
| + | |
- | |-
| + | |
- | |f'(x<sub>0</sub>)
| + | |
- | |f'(x<sub>1</sub>)
| + | |
- | |…
| + | |
- | |f'(x<sub>m</sub>)
| + | |
- | |-
| + | |
- | |…
| + | |
- | |-
| + | |
- | |f<sup>(a<sub>0</sub> − 1)</sup>(x<sub>0</sub>)
| + | |
- | |f<sup>(a<sub>1</sub> − 1)</sup>(x<sub>1</sub>)
| + | |
- | |…
| + | |
- | |f<sup>(a<sub>m</sub> − 1)</sup>(x<sub>m</sub>)
| + | |
- | |}
| + | |
- | | + | |
- | * a<sub>i</sub> ∈ N ( натуральное), i = 0…m
| + | |
- | * a<sub>i</sub> — кратность i-го узла
| + | |
- | | + | |
- | Цель: построить H<sub>n</sub>(x)
| + | |
- | | + | |
- | Замечание. H<sub>n</sub><sup>(i)</sup> = f<sup>(i)</sup>(x<sub>k</sub>), k = 0…m, i = 0…a<sub>k</sub> − 1 (1)
| + | |
- | | + | |
- | При выполнении условия a<sub>0</sub> + a<sub>1</sub> + … + a<sub>m</sub> = n + 1 мы можем построить полином Эрмита, причём единственный.
| + | |
- | | + | |
- | == Общий вид полинома Эрмита ==
| + | |
- | H<sub>n</sub>(x) = ∑<sub>k = 0</sub><sup>m</sup> ∑<sub>i = 0</sub><sup>a<sub>k</sub> − 1</sup> c<sub>k, i</sub>(x)f<sup>(i)</sup>(x<sub>k</sub>)
| + | |
- | * c<sub>k, i</sub>(x) — полином n-й степени
| + | |
- | * x<sub>i</sub> — различные
| + | |
- | | + | |
- | == H<sub>3</sub>(x) ==
| + | |
- | H<sub>3</sub>(x) = c<sub>0</sub>(x)f(x<sub>0</sub>) + c<sub>1</sub>(x)f(x<sub>1</sub>) + c<sub>2</sub>(x)f(x<sub>2</sub>) + b<sub>1</sub>(x)f'(x<sub>1</sub>)
| + | |
- | * c<sub>0</sub>(x) = ((x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>2</sub>))/((x<sub>0</sub> − x<sub>1</sub>)<sup>2</sup>(x<sub>0</sub> − x<sub>2</sub>))
| + | |
- | * c<sub>2</sub>(x) = ((x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>0</sub>))/((x<sub>2</sub> − x<sub>1</sub>)<sup>2</sup>(x<sub>2</sub> − x<sub>0</sub>))
| + | |
- | * b<sub>1</sub>(x) = ((x − x<sub>0</sub>)(x − x<sub>1</sub>)(x − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>))
| + | |
- | * c<sub>1</sub>(x) = (x − x<sub>0</sub>)(x − x<sub>2</sub>)/((x<sub>1</sub> − x<sub>0</sub>)<sup>2</sup>(x<sub>1</sub> − x<sub>2</sub>)<sup>2</sup>)) × [1 − ((x − x<sub>1</sub>)(2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>))]
| + | |
- | | + | |
- | == Погрешность полинома Эрмита ==
| + | |
- | * ψ<sub>H<sub>3</sub></sub>(x) = f(x) − H<sub>3</sub>(x) = f<sup>(4)</sup>(ξ)/4!
| + | |
- | * M<sub>4</sub> = sup<sub>x<sub>0</sub> ≤ x ≤ x<sub>2</sub></sub> |f<sup>(4)</sup>(x)|
| + | |
- | * |f(x) − H<sub>3</sub>(x)| ≤ M<sub>4</sub>/4! × |ω(x)|
| + | |
- | | + | |
- | == Формула Симпсона ==
| + | |
- | Пусть требуется найти ∫<sub>a</sub><sup>b</sup> f(x)dx, f(x<sub>i</sub>) = f<sub>i</sub>, f(x<sub>i</sub>+0,5h) = f<sub>i + 1/2</sub>
| + | |
- | | + | |
- | По формуле Симпсона:
| + | |
- | * ∫<sub>x<sub>i − 1</sub></sub><sup>x<sub>i</sub></sup> f(x)dx ≈ h/6 × (f<sub>i − 1</sub> + 4f<sub>i − 1/2</sub> + f<sub>i</sub>)
| + | |
- | | + | |
- | == Оценка погрешности формулы Симпсона ==
| + | |
- | * M<sub>4</sub> = sup<sub>a ≤ x ≤ b</sub> |f<sup>(4)</sup>(x)|
| + | |
- | * Ψ<sub>h</sub>(f) ≤ (h/2)<sup>4</sup> (M<sub>4</sub>(b − a))/180 = O(h<sup>4</sup>)
| + | |
- | | + | |
- | == L<sub>2</sub> для функций ==
| + | |
- | Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫<sub>a</sub><sup>b</sup> f<sup>2</sup>(x)dx < ∞, f ∈ L<sub>2</sub>. В этом функциональном пространстве вводим векторное произведение: ∀ f, g ∈ L<sub>2</sub>: (f, g) = ∫<sub>a</sub><sup>b</sup> f(x)g(x)dx. Норма: ||f|| = (f, f)<sup>1/2</sup> = (∫<sub>a</sub><sup>b</sup> f<sup>2</sup>(x)dx)<sup>1/2</sup>. Эта норма не согласована с нормой в дискретном L<sub>2</sub>.
| + | |
- | | + | |
- | == Наилучшее среднеквадратичное приближение ==
| + | |
- | * Требуется найти такой обобщённый многочлен <span style="border-top:solid 1px">φ</span>(x) = ∑<sub>k = 0</sub><sup>n</sup> c_<sub>k</sub>φ<sub>k</sub>(x), что
| + | |
- | ** ||f − <span style="border-top:solid 1px">φ</span>(x)|| = ∫<sub>a</sub><sup>b</sup> (f(x) − <span style="border-top:solid 1px">φ</span>(x))<sup>2</sup>dx = min<sub>φ(x)</sub>||f − φ(x)||<sub>L<sub>2</sub></sub><sup>2</sup>
| + | |
- | | + | |
- | == Отклонение ==
| + | |
- | ∫<sub>a</sub><sup>b</sup> (f(x) − ∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub>φ<sub>k</sub>(x))<sup>2</sup>dx = ∫<sub>a</sub><sup>b</sup> f(x)<sup>2</sup>dx − 2∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub> ∫<sub>a</sub><sup>b</sup> f(x)φ<sub>0</sub>(x)dx + ∑<sub>l = 0</sub><sup>n</sup> c<sub>l</sub> ∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub> ∫<sub>a</sub><sup>b</sup> φ<sub>0</sub><sup>2</sup>(x)dx = ∫<sub>a</sub><sup>b</sup> f(x)<sup>2</sup>dx − ∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> ≥ 0
| + | |
- | * ∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> ≤ ||f||<sup>2</sup> — неравенство Бесселя
| + | |
- | * ∑<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> = ||f||<sup>2</sup> — равенство Парсеваля
| + | |
- | | + | |
- | = Глава 3 =
| + | |
- | == Нелинейная система ==
| + | |
- | {|
| + | |
- | |rowspan = "4"|{
| + | |
- | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |-
| + | |
- | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |-
| + | |
- | |…
| + | |
- | |-
| + | |
- | |f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |}
| + | |
- | | + | |
- | * f: R<sub>m</sub> → R<sub>m</sub>
| + | |
- | * f_ = (f<sub>1</sub>, …, f<sub>m</sub>)<sup>T</sup>
| + | |
- | * x_ = (x<sub>1</sub>, …, x<sub>m</sub>)<sup>T</sup>
| + | |
- | * f_ (x_) = 0
| + | |
- | | + | |
- | == Задачи связанные с решением нелинейных уравнений и систем ==
| + | |
- | # Локализация корня x<sub>*</sub>, f(x<sub>*</sub>) = 0, указать область, где он находится. Этим мы заниматься не будем
| + | |
- | # Строится итерационный процесс, и аккуратно выбирая начальное приближение x<sub>0</sub> из локализованной области, x<sub>n</sub> → x<sub>*</sub>, n → ∞
| + | |
- | | + | |
- | == Метод бисекции решения нелинейного уравнения ==
| + | |
- | Второй метод более регулярный и он называется метод бисекции.
| + | |
- | * f(a) < 0
| + | |
- | * f(b) > 0
| + | |
- | * Берётся x<sub>0</sub> = (a + b)/2
| + | |
- | * Если f(x<sub>0</sub>) > 0, то x<sub>*</sub> ∈ (a, x<sub>0</sub>)
| + | |
- | Каждый раз мы сужаем в два раза промежуток, где находится корень
| + | |
- | | + | |
- | == Метод простой итерации (МПИ) ==
| + | |
- | * f(x) = 0 (1)
| + | |
- | * x<sub>*</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) (по определению)
| + | |
- | * x = S(x) (2)
| + | |
- | * x<sub>n + 1</sub> = S(x<sub>n</sub>) (3)
| + | |
- | * x<sub>0</sub> ∈(x<sub>*</sub>)
| + | |
- | | + | |
- | S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ U<sub>a</sub>(x<sub>*</sub>).
| + | |
- | | + | |
- | == Условие наличия корня в отрезке при использовании МПИ ==
| + | |
- | Если известно, что ∃ S'(x), и sup<sub>x ∈ U<sub>a</sub>(x<sub>*</sub>)</sub> |S'(x)| = q < 1, то МПИ сходится, x<sub>0</sub> ∈ U<sub>a</sub>(x<sub>*</sub>)
| + | |
- | | + | |
- | == Специальный вид МПИ ==
| + | |
- | (x<sub>n + 1</sub> − x<sub>n</sub>)/τ + f(x<sub>n</sub>) = 0, τ > 0, x<sub>0</sub> ∈ U<sub>a</sub>(x<sub>*</sub>), n = 0, 1, 2, …
| + | |
- | | + | |
- | == Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии ==
| + | |
- | −1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M<sub>1</sub>
| + | |
- | | + | |
- | == Метод Эйткена ==
| + | |
- | Предположим, что x<sub>n</sub> − x<sub>*</sub> = Aq<sup>n</sup> (6). Запишем три итерации:
| + | |
- | * x<sub>n − 1</sub> − x<sub>*</sub> = Aq<sup>n − 1</sup> (7)
| + | |
- | * x<sub>n</sub> − x<sub>*</sub> = Aq<sup>n</sup> (8)
| + | |
- | * x<sub>n + 1</sub> − x<sub>*</sub> = Aq<sup>n +1</sup> (9)
| + | |
- | Тогда:
| + | |
- | * x<sub>*</sub> = x<sub>n</sub> − ((x<sub>n + 1</sub> − x<sub>n</sub>)<sup>2</sup>)/(x<sub>n + 1</sub> − 2x<sub>n</sub> + x<sub>n − 1</sub>)
| + | |
- | Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.
| + | |
- | | + | |
- | == Метод Ньютона (касательных) ==
| + | |
- | * f(x) = 0
| + | |
- | * x<sub>*</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) (по определению)
| + | |
- | * x<sup>n</sup> — n-я итерация
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> — начальное приближение (2)
| + | |
- | * От функции требуется гладкость до третьей производной
| + | |
- | Метод Ньютона очень быстро сходится, но он может зацикливаться.
| + | |
- | | + | |
- | == Модифицированный метод Ньютона ==
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, …, x<sup>0</sup> — начальная итерация
| + | |
- | * Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания
| + | |
- | | + | |
- | == Метод Ньютона для системы из 2 уравнений ==
| + | |
- | {|
| + | |
- | |rowspan= "2"|{
| + | |
- | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0
| + | |
- | |rowspan="2"| (3)
| + | |
- | |-
| + | |
- | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0
| + | |
- | |}
| + | |
- | | + | |
- | (x<sub>1</sub><sup>*</sup>, x<sub>2</sub><sup>*</sup>) — решение
| + | |
- | | + | |
- | {|
| + | |
- | |rowspan= "2"|J(x) = (
| + | |
- | |(δf<sub>1</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
| + | |
- | |(δf<sub>1</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
| + | |
- | |rowspan= "2"|)
| + | |
- | |-
| + | |
- | |(δf<sub>2</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
| + | |
- | |(δf<sub>2</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
| + | |
- | |}
| + | |
- | | + | |
- | * ∃ J<sup>−1</sup>(x<sup>n</sup>)
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − J<sup>−1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> ∈ U<sub>a</sub>(x<sup>*</sup>)
| + | |
- | | + | |
- | == Метод Ньютона: общий случай для m уравнений ==
| + | |
- | {|
| + | |
- | |rowspan= "4"|{
| + | |
- | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |rowspan="4"| (6)
| + | |
- | |-
| + | |
- | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |-
| + | |
- | |…
| + | |
- | |-
| + | |
- | |f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0
| + | |
- | |-
| + | |
- | |}
| + | |
- | | + | |
- | * (J(x))<sub>ij</sub> = (δf<sub>i</sub>/δx<sub>j</sub>), i, j = 1…m
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − J<sup>−1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> ∈ U<sub>a</sub>(x<sup>*</sup>) (6)
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − J(x<sup>0</sup>)f(x<sup>n</sup>)
| + | |
- | | + | |
- | == Метод секущей (хорд) ==
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, …
| + | |
- | * f'(x<sup>n</sup>) = (f(x<sup>n + 1</sup>) − f(x<sup>n</sup>))/(x<sup>n + 1</sup> − x<sup>n</sup>)
| + | |
- | | + | |
- | == Комбинированный метод ==
| + | |
- | Подставим в метод Ньютона приближение производной:
| + | |
- | * x<sup>n + 1</sup> = x<sup>n</sup> − (x<sup>n</sup> − x<sup>n − 1</sup>)f(x<sup>n</sup>)/(f(x<sup>n</sup>) − f(x<sup>n − 1</sup>))
| + | |
- | | + | |
- | == Скорость сходимости метода Ньютона ==
| + | |
- | * Z<sub>n</sub> = x<sup>n</sup> − x<sub>*</sub> — погрешность
| + | |
- | * ∃ M > 0: 0,5|S''(x~<sub>n</sub>)| ≤ M
| + | |
- | * |Z<sub>n</sub>| ≤ (M|Z<sub>0</sub>|)<sup>2<sup>n</sup></sup>/M = 1/M × q<sup>2<sup>n</sup></sup>
| + | |
- | | + | |
- | == Скорость сходимости модифицированного метода Ньютона ==
| + | |
- | * S'(x) = 1 − f'(x)/f'(x<sup>0</sup>)
| + | |
- | * S'(x<sub>*</sub>) = 1 − f'(x<sub>*</sub>)/f'(x<sub>0</sub>)
| + | |
- | Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.
| + | |
- | | + | |
- | {{Курс Численные Методы}}
| + | |