Численные Методы, Определения
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(→Соотношение сложностей методов Якоби и Зейделя) |
||
(11 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | == | + | = Глава 1 = |
- | + | == Система линейных алгебраических уравнений (СЛАУ) == | |
- | + | '''Система линейных алгебраических уравнений:''' | |
- | + | * Ax = f | |
+ | * 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>) | ||
+ | Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона. | ||
+ | |||
+ | {{Курс Численные Методы}} |
Текущая версия
[править] Глава 1
[править] Система линейных алгебраических уравнений (СЛАУ)
Система линейных алгебраических уравнений:
- Ax = f
- A (m × m), det A ≠ 0 — решение есть, оно единственное
- x = (x1, x2, ... xm)T
- f = (f1, f2, ... fm)T
[править] Группы методов решения СЛАУ
К курсе рассматриваются две группы методов:
- Прямые (точные) методы
- Итерационные (приближённые) методы
[править] Прямой метод решения СЛАУ
Прямой метод решения СЛАУ — метод, который позволяет реализовать в алгоритме определённые формулы, то есть аналитическое решение.
[править] Задача на собственные значения
Задача на собственные значения — задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение.
[править] Факторизация матрицы
Факторизация матрицы — представление матрицы А в виде произведения B × C, где
B — нижнетреугольная матрица:
| C — верхнетреугольная матрица с единицами на диаонали:
|
[править] В каком порядке ищутся элементы матриц B и C при факторизации А = B × C
Процесс нахождения матриц B и C размерами m × m разбивается на m этапов, причём на каждом этапе сначала по формуле bij = aij − Σl=1j−1 bil×clj находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.
[править] Условие существования и единственности разложения А = B × C
Все главные угловые миноры A отличны от 0:
A1 = a11 ≠ 0 | ; |
| ; | …; |
|
[править] Связь метода Гаусса с разложением A = B × C
Три этапа метода Гаусса соответствуют трём этапам факторизации:
- В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется (m3 − m)/3 операций — то же количество действий требуется для нахождения матриц B и C
- Для решения уравнения By = f требуется m(m + 1)/2 действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
- Для решения уравнения Cx = y требуется m(m − 1)/2 действий — в точности то число действий, которое требуется для обратного хода Гаусса
[править] Метод Гаусса-Жордана
Метод Гаусса-Жордана:
- Обозначим A−1 = X. Тогда AX = E
- Запишем в явном виде:
- ∑l = 1mailxlj = δij, i, j = 1..m
- m2 неизвестных, поэтому действий m6
- Разумно организовав алгоритм, можно получить порядка m3 действий
[править] Метод квадратного корня (метод Холецкого)
- Решаем уравнение Ax = f
- |A| ≠ 0 (m × m)
- A = A* ⇔ aij = aji
- A = AT — для вещественных матриц
Факторизуем матрицу A в виде A = S*DS
s11 | s12 | s13 | ... | s1m | |
0 | s22 | s23 | ... | s2m | |
S = | 0 | 0 | s33 | .. | s3m |
... | |||||
0 | 0 | 0 | ... | smm |
sii > 0, i = 2…m
D = diag (d11, …, dmm) dii = ±1, i = 1..m
Тогда система решается следующим образом:
- S*DSx = f
- S*Dy = f
- Sx = y
Эти две системы решаются явным образом, ибо матрицы треугольные.
[править] Достоинства и недостатки метода квадратного корня
Плюс:
- Количество действий сокращается в два раза (m3/6 умножений и делений + m извлечений корня)
Минусы:
- Только для эрмитовых матриц
[править] Что значит «решить СЛАУ итерационным методом»
- xin — i-я кордината, n-я итерация
- x0 — начальное приближение
Далее организуется процесс так, что limn → ∞xn → x, то есть, в некоторой норме |xn − x| < ε, ε > 0
[править] Вопросы, рассматриваемые при исследовании итерационного метода
- Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
- С какой скоростью
[править] Метод Якоби
- xin + 1 = fi/aii − ∑j = 1i − 1 aij/aiixjn − ∑j = i + 1m aij/aiixjn, n ∈ ℕ ∪ {0}
- x0 — задано
[править] Достоинства и недостатки метода Якоби
Плюс:
- Данный метод реализуется достаточно просто
Минус:
- Очень медленная сходимость
[править] Метод Зейделя
- xin + 1 = fi/aii − ∑j = 1i − 1 aij/aiixjn + 1 − ∑j = i + 1m aij/aiixjn, n ∈ ℕ ∪ {0} (3)
- x0 — задано
[править] Соотношение сложностей методов Якоби и Зейделя
По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации
[править] Двуслойная запись
Двуслойная запись — когда связываются две соседние итерации.
[править] Каноническая форма записи двуслойного итерационного метода решения СЛАУ
Определение. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m × m), det A ≠ 0 называется его запись в виде:
- Bn + 1 (xn + 1 − xn)/τn + 1 + Axn = f (4)
где
- τn + 1 > 0, n ∈ ℕ ∪ {0}
- x0 — задано
- ∃Bn + 1−1
[править] Виды итерационных методов
- Метод явный, если Bn + 1 = E. Если матрица диагональная, то тоже явный.
- Метод стационарный, если
- Bn + 1 = B
- τn + 1 = τ
[править] Метод простой итерации
Метод простой итерации (МПИ):
- (МПИ) (xn+1 − xn)/τ + Axn = f, x0 — задано, n ∈ ℕ ∪ {0}, τ > 0
- Если τ меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.
[править] Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)
- A = R1 + R2, где R1 — нижнетреугольная матрица с диагональными элементам r1ii = aii/2, R2 — верхнетреугольная матрица с диагональными элементам r2ii = aii/2.
- (E + ωR1)(E + ωR2)((xn + 1 − xn)/τ) + Axn = f (5)
- n ∈ ℕ ∪ {0}, x0 задано, ω > 0, τ > 0
- Применительно к канонической записи B = (E + ωR1)(E + ωR2)
[править] Невязка
rn = f − Axn
[править] Энергетическая норма
Энергетическая норма ||x||D = (Dx,x)1/2, где D — положительно определённый опрератор, то есть (Dx, x) > 0, ∀ x ≠ 0.
[править] Вектор погрешности
Вектор погрешности: vn = xn − x.
[править] Матрица перехода
S = E − τB−1A
Вывод:
- Ax = f
- ∃ A−1 (m × m)
- B (xn + 1 − xn)/τ + Axn = f
- xn = vn + x
- B (vn + 1 − vn)/τ + Avn = 0
- (vn + 1 − vn)/τ + B−1Avn = 0
- vn+1 = vn − τB−1Avn = (E − τB−1A)vn
- S = E − τB−1A
[править] Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода
Теорема 1. Итерационный метод B (xn + 1 − xn)/τ + Axn = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E − τB−1A по модулю меньше 1: |λkS| < 1.
Это означает, что оператор S — сжимающий.
[править] Достаточное условие сходимости итерационного метода (теорема Самарского)
Теорема (Самарского, о достаточном условии сходимости метода B (xn + 1 − xn)/τ + Axn = f). Пусть есть A = A* = AT > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||xn − x|| = (∑i = 1m (xin − xi)2)1/2 → 0, n → ∞.
[править] Теорема о сходимости метода Якоби
Следствие 1 теоремы Самарского. Пусть ∃ A = A* > 0, 2D > A. Тогда Методя Якоби сходится при любом начальном приближении.
[править] Теорема о сходимости метода простой итерации
Следствие 3 теоремы Самарского. Пусть ∃ A = A* > 0, γ2 = max1 ≤ x ≤ mλkA > 0. Тогда 0 < τ < 2/γ2 МПИ сходится при ∀ x0
[править] Теорема о сходимости метода Зейделя
Следствие 4. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме. Вообще достаточно только самосопряженности оператора А: A = A* > 0
[править] Скорость сходимости итерационного метода
ln 1/ρ — скорость сходимости итерационного метода
[править] Оценка скорости сходимости итерационного метода
Теорема (об оценке скорости сходимости итерационного метода). Пусть
- A = A* > 0
- B = B* > 0
- 0 < ρ < 1
- 1 − ρ/τB ≤ A ≤ 1 + ρ/τB
Тогда итерационный метод B (xn + 1 − xn)/τ + Axn = f сходится к решению СЛАУ Ax = f и имеет место оценка ||vn + 1||B ≤ ρ||vn||
[править] Равенство Парсеваля
Равенство Парсеваля Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑k = 1mckek.
Тогда равенство Парсиваля есть ||x||2 = ∑k = 1mck2
[править] Оценка скорости сходимости МПИ
Следствие 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+1 − x|| ≤ ρ||xn − x||
[править] Теорема о сходимости ПТИМ
Теорема (о сходимости ПТИМ). Пусть A = A* > 0, ω > τ/4. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.
[править] Теорема об оценке скорости сходимости ПТИМ
Теорема (об оценке скорости сходимости ПТИМ). Пусть A = A* > 0. Пусть существуют такие две константы δ > 0, Δ > 0:
- A ≥ δE, R2*R2 ≤ Δ/4 A (2)
- Положим ω = 2/√δΔ, τ = 2/γ1 + γ2, γ1 = √δ/2 (√δΔ/√δ+√Δ); γ2 = √δΔ/4
- ||xn + 1 − x||B ≤ ρ ||xn − x||B
- где B = (E + ωR2*)(E + ωR2), ρ = 1 − √η/1 + 3√η, η = δ/Δ
- R2* = R1
[править] Оценка скорости сходимости для метода простой итерации
- ||xn + 1 − x|| ≤ ρ ||xn − x||, ρ = 1 − ξ/1 + ξ, ξ = γ1/γ2, ξ = η = O(m−2)
- 1/ρ = 1 + η/1 − η ≈ (1 + η)2 ≈ 1 + 2η
- ln 1/ρ ≈ η, n0(ε) = O(m2)
[править] Задача на собственные значения
Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)
- λ — собственные значения
- x — собственные вектора
Два круга проблем:
- Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
- Полная проблема собственных значений — нужно находить все собственные значения
Всего m значений (с учётом кратности): λk, k = 1..m
Вообще говоря, собственные значения комплексные.
Все методы итерационные. Один из самых простых методов — степенной метод.
[править] Степенной метод нахождения собственных значений
Степенной метод — метод, который описывается уравнением 1:
- xn + 1 = Axn (1)
- n = 0, 1, ..., x0 — начальное приближение
- xn = Anx0
[править] Условия для степенного метода
- Предположения относительно матрицы A:
- Все собственные значения расположены в порядке неубывания модуля: |λ1| ≤ |λ2| ≤ |λ3| ≤ ... ≤ |λm|
- Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {ek}1m — базис из собственных векторов A (Aek = λkek, k = 1..m)
- Ограничение B: последнее собственное значение не является кратным: |(λm − 1)/(λm) < 1
- Ограничение C: ∀ x = c1e1 + ... + cmem, cm ≠ 0
[править] Метод обратных итераций
- ∃ A−1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
- Axn + 1 = xn, n = 0, 1, …, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
- xn + 1 = A−1xn (4)
- xn = (A−1)nxn
Условия:
A) ∃ {ek}1m из СВ
B) |λ1/λ2| < 1
C) x0 = c1e1+ … + cmem, c1 ≠ 0
Тогда:
- xn = c1λ1−ne1+ … + cmλm−nem
- xn/e1λ1−n = e1 + … + (cm/c1)(λ1/λm)nem
[править] Метод обратных итераций со сдвигом
- (A − αE)xn + 1 = xn (5)
- n = 0, 1, …, x0 — начальное приближение, α ∈ R
- ∃ (A − αE)−1
- xn + 1 = (A − αE)−1xn
- xn = el
- 1/|λl − α| = max1 ≤ k ≤ m 1/|λk − α|
[править] Что такое верхняя почти треугольная форма
Верхняя почти треугольная форма — форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.
[править] Преобразование элементарных отражений (преобразование Хаусхолдера)
Определение. Преобразование элементарных отражений (Преобразование Хаусхолдера). Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vvT/||v||2
[править] QR-алгоритм решения полной проблемы собственных значений
∀ A = Q × R, Q−1 = QT, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.
[править] Количество действий для работы QR-алгоритма
- полная — O(m3)
- ВПТФ — O(m2)
- А - трехдиагональная - O(m)
[править] Теорема о сохранении ВПТФ
Пусть C = B × A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.
[править] Глава 2
[править] Задача интерполяции
Суть задачи: есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x0 < x1 < x2 < … < xn ≤ b — {xi}0n — узлы интерполирование (n + 1 штук). Есть f(xi) = fi, i = 0…n. Если полином Pn(x) = a0 + a1x + … anxn такой, что Pn(xi) = f(xi), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).
[править] Интерполяционный полином
Если полином Pn(x) = a0 + a1x + … anxn такой, что Pn(xi) = f(xi), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).
[править] Существование и единственность интерполяционного полинома
При условиях, накладываемых в постановке задачи интерполяции (узлы интерполирования не совпадают) интерполяционный полином существует и единственный.
[править] Интерполяционный полином в форме Лагранжа
Ln(x) = ∑k = 0n(ω(x))/((x −xk)ω'(xk)) × f(xk), где
- ω(x) = (x − x0)(x − x1)…(x − xn) = ∏i = 0n(xi − xj)
- ω(x) = [ ](x − xk)
- ω'(x) = [ ] + [ ]'(x − xk)
- ω'(xk) = ∏k ≠ jn(xk − xj)
[править] Определение погрешности интерполяционного полинома
Погрешность интерполяционной формулы Лагранжа ψLn(x) = f(x) − Ln(x). Во всех узлах она будет совпадать: ψLn(xi) = 0.
Замечание 1. Если f(x) — полином степени ≤ n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.
Замечание 2. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.
[править] Разделённая разность
Разделённой разностью первого порядка, построенной по узлам xi, xj называется отношение f(xi, xj) = (f(xj) − f(xi)/(xj − xi))
Разделённая разность k+1-го порядка: пусть есть f(xj, xj + 1, …, xj + k), f(xj + 1, xj + 2, …, xj + k + 1) — разности k-го порядка. Тогда f(xj, xj + 1, …, xj + k + 1) = (f(xj + 1, xj + 2, …, xj + k + 1) − f(xj, xj + 1, …, xj + k))/(xj + k + 1 − xj) — разделённая разность k + 1-го порядка.
[править] Выражение разделённой разности через значения функции в точках
Разделённая разность k-го порядка, построенная по узлам x0, … xk может быть записана как f(x0, x1, …, xk) = ∑i = 0k(f(xi))/(ω0, k'(xi))
[править] Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка
f(xk) = f(x0) + (xk − x0)f(x0, x1) + (xk − x0)(xk − x1)f(x0, x1, x2) + … + (xk − x0)(xk − x1)…(xk − xk − 1)f(x0, x1, …, xk)
[править] Интерполяционная функция в форме Ньютона
Nn(x) = f(x0) + (x − x0)f(x0, x1) + (x − x0)(x − x1)f(x0, x1, x2) + … + (x − x0)(x − x1)…(x − xn − 1)f(x0, x1, …, xn)
[править] Погрешность интерполяционной формулы Ньютона
Погрешность та же самая, но записана внешне по-другому:
|ψNn(x)| = |f(x) − Nn(x)| ≤ Mn + 1/(n + 1)! × |ω(x)|, Mn + 1 = supa ≤ x≤ b |f(x)(n + 1)|
== Когда лучше использовать Ньютона, а когда — Лагранжа
- Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
- Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах
[править] Интерполяционная формула Эрмита
Пусть у нас есть узлы x0, … xm — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:
x0 | x1 | … | xm |
f(x0) | f(x1) | … | f(xm) |
f'(x0) | f'(x1) | … | f'(xm) |
… | |||
f(a0 − 1)(x0) | f(a1 − 1)(x1) | … | f(am − 1)(xm) |
- ai ∈ N ( натуральное), i = 0…m
- ai — кратность i-го узла
Цель: построить Hn(x)
Замечание. Hn(i) = f(i)(xk), k = 0…m, i = 0…ak − 1 (1)
При выполнении условия a0 + a1 + … + am = n + 1 мы можем построить полином Эрмита, причём единственный.
[править] Общий вид полинома Эрмита
Hn(x) = ∑k = 0m ∑i = 0ak − 1 ck, i(x)f(i)(xk)
- ck, i(x) — полином n-й степени
- xi — различные
[править] H3(x)
H3(x) = c0(x)f(x0) + c1(x)f(x1) + c2(x)f(x2) + b1(x)f'(x1)
- c0(x) = ((x − x1)2(x − x2))/((x0 − x1)2(x0 − x2))
- c2(x) = ((x − x1)2(x − x0))/((x2 − x1)2(x2 − x0))
- b1(x) = ((x − x0)(x − x1)(x − x2))/((x1 − x0)(x1 − x2))
- c1(x) = (x − x0)(x − x2)/((x1 − x0)2(x1 − x2)2)) × [1 − ((x − x1)(2x1 − x0 − x2))/((x1 − x0)(x1 − x2))]
[править] Погрешность полинома Эрмита
- ψH3(x) = f(x) − H3(x) = f(4)(ξ)/4!
- M4 = supx0 ≤ x ≤ x2 |f(4)(x)|
- |f(x) − H3(x)| ≤ M4/4! × |ω(x)|
[править] Формула Симпсона
Пусть требуется найти ∫ab f(x)dx, f(xi) = fi, f(xi+0,5h) = fi + 1/2
По формуле Симпсона:
- ∫xi − 1xi f(x)dx ≈ h/6 × (fi − 1 + 4fi − 1/2 + fi)
[править] Оценка погрешности формулы Симпсона
- M4 = supa ≤ x ≤ b |f(4)(x)|
- Ψh(f) ≤ (h/2)4 (M4(b − a))/180 = O(h4)
[править] L2 для функций
Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫ab f2(x)dx < ∞, f ∈ L2. В этом функциональном пространстве вводим векторное произведение: ∀ f, g ∈ L2: (f, g) = ∫ab f(x)g(x)dx. Норма: ||f|| = (f, f)1/2 = (∫ab f2(x)dx)1/2. Эта норма не согласована с нормой в дискретном L2.
[править] Наилучшее среднеквадратичное приближение
- Требуется найти такой обобщённый многочлен φ(x) = ∑k = 0n c_kφk(x), что
- ||f − φ(x)|| = ∫ab (f(x) − φ(x))2dx = minφ(x)||f − φ(x)||L22
[править] Отклонение
∫ab (f(x) − ∑k = 0n ckφk(x))2dx = ∫ab f(x)2dx − 2∑k = 0n ck ∫ab f(x)φ0(x)dx + ∑l = 0n cl ∑k = 0n ck ∫ab φ02(x)dx = ∫ab f(x)2dx − ∑k = 0n ck2 ≥ 0
- ∑k = 0n ck2 ≤ ||f||2 — неравенство Бесселя
- ∑k = 0n ck2 = ||f||2 — равенство Парсеваля
[править] Глава 3
[править] Нелинейная система
{ | f1(x1, x2, …, xm) = 0 |
f2(x1, x2, …, xm) = 0 | |
… | |
fm(x1, x2, …, xm) = 0 |
- f: Rm → Rm
- f_ = (f1, …, fm)T
- x_ = (x1, …, xm)T
- f_ (x_) = 0
[править] Задачи связанные с решением нелинейных уравнений и систем
- Локализация корня x*, f(x*) = 0, указать область, где он находится. Этим мы заниматься не будем
- Строится итерационный процесс, и аккуратно выбирая начальное приближение x0 из локализованной области, xn → x*, n → ∞
[править] Метод бисекции решения нелинейного уравнения
Второй метод более регулярный и он называется метод бисекции.
- f(a) < 0
- f(b) > 0
- Берётся x0 = (a + b)/2
- Если f(x0) > 0, то x* ∈ (a, x0)
Каждый раз мы сужаем в два раза промежуток, где находится корень
[править] Метод простой итерации (МПИ)
- f(x) = 0 (1)
- x* ∈ Ua(x*) (по определению)
- x = S(x) (2)
- xn + 1 = S(xn) (3)
- x0 ∈(x*)
S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ Ua(x*).
[править] Условие наличия корня в отрезке при использовании МПИ
Если известно, что ∃ S'(x), и supx ∈ Ua(x*) |S'(x)| = q < 1, то МПИ сходится, x0 ∈ Ua(x*)
[править] Специальный вид МПИ
(xn + 1 − xn)/τ + f(xn) = 0, τ > 0, x0 ∈ Ua(x*), n = 0, 1, 2, …
[править] Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии
−1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M1
[править] Метод Эйткена
Предположим, что xn − x* = Aqn (6). Запишем три итерации:
- xn − 1 − x* = Aqn − 1 (7)
- xn − x* = Aqn (8)
- xn + 1 − x* = Aqn +1 (9)
Тогда:
- x* = xn − ((xn + 1 − xn)2)/(xn + 1 − 2xn + xn − 1)
Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.
[править] Метод Ньютона (касательных)
- f(x) = 0
- x* ∈ Ua(x*) (по определению)
- xn — n-я итерация
- xn + 1 = xn − f(xn)/f'(xn), n = 0, 1, …, x0 — начальное приближение (2)
- От функции требуется гладкость до третьей производной
Метод Ньютона очень быстро сходится, но он может зацикливаться.
[править] Модифицированный метод Ньютона
- xn + 1 = xn − f(xn)/f'(x0), n = 0, 1, …, x0 — начальная итерация
- Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания
[править] Метод Ньютона для системы из 2 уравнений
{ | f1(x1, x2) = 0 | (3) |
f2(x1, x2) = 0 |
(x1*, x2*) — решение
J(x) = ( | (δf1/δx1)(x1n, x2n) | (δf1/δx2)(x1n, x2n) | ) |
(δf2/δx1)(x1n, x2n) | (δf2/δx2)(x1n, x2n) |
- ∃ J−1(xn)
- xn + 1 = xn − J−1(xn)f(xn), n = 0, 1, …, x0 ∈ Ua(x*)
[править] Метод Ньютона: общий случай для m уравнений
{ | f1(x1, x2, …, xm) = 0 | (6) |
f2(x1, x2, …, xm) = 0 | ||
… | ||
fm(x1, x2, …, xm) = 0 |
- (J(x))ij = (δfi/δxj), i, j = 1…m
- xn + 1 = xn − J−1(xn)f(xn), n = 0, 1, …, x0 ∈ Ua(x*) (6)
- xn + 1 = xn − J(x0)f(xn)
[править] Метод секущей (хорд)
- xn + 1 = xn − f(xn)/f'(x0), n = 0, 1, …
- f'(xn) = (f(xn + 1) − f(xn))/(xn + 1 − xn)
[править] Комбинированный метод
Подставим в метод Ньютона приближение производной:
- xn + 1 = xn − (xn − xn − 1)f(xn)/(f(xn) − f(xn − 1))
[править] Скорость сходимости метода Ньютона
- Zn = xn − x* — погрешность
- ∃ M > 0: 0,5|S''(x~n)| ≤ M
- |Zn| ≤ (M|Z0|)2n/M = 1/M × q2n
[править] Скорость сходимости модифицированного метода Ньютона
- S'(x) = 1 − f'(x)/f'(x0)
- S'(x*) = 1 − f'(x*)/f'(x0)
Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.