Материал из eSyr's wiki.

Версия 03:16, 19 декабря 2011 (править) 78.106.11.212 (Обсуждение) (→Метод обратных итераций со сдигом) ← К предыдущему изменению		Текущая версия (22:48, 4 ноября 2014) (править) (отменить) 93.74.247.195 (Обсуждение) (→Соотношение сложностей методов Якоби и Зейделя)
Строка 197:		Строка 197:
	== Соотношение сложностей методов Якоби и Зейделя ==		== Соотношение сложностей методов Якоби и Зейделя ==
-	По сложности и скорости сходимости эти два метода одинаковы.	+	По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации
	== Двуслойная запись ==		== Двуслойная запись ==

---

Текущая версия

Содержание 1 Глава 1 1.1 Система линейных алгебраических уравнений (СЛАУ) 1.2 Группы методов решения СЛАУ 1.3 Прямой метод решения СЛАУ 1.4 Задача на собственные значения 1.5 Факторизация матрицы 1.6 В каком порядке ищутся элементы матриц B и C при факторизации А = B × C 1.7 Условие существования и единственности разложения А = B × C 1.8 Связь метода Гаусса с разложением A = B × C 1.9 Метод Гаусса-Жордана 1.10 Метод квадратного корня (метод Холецкого) 1.11 Достоинства и недостатки метода квадратного корня 1.12 Что значит «решить СЛАУ итерационным методом» 1.13 Вопросы, рассматриваемые при исследовании итерационного метода 1.14 Метод Якоби 1.15 Достоинства и недостатки метода Якоби 1.16 Метод Зейделя 1.17 Соотношение сложностей методов Якоби и Зейделя 1.18 Двуслойная запись 1.19 Каноническая форма записи двуслойного итерационного метода решения СЛАУ 1.20 Виды итерационных методов 1.21 Метод простой итерации 1.22 Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ) 1.23 Невязка 1.24 Энергетическая норма 1.25 Вектор погрешности 1.26 Матрица перехода 1.27 Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода 1.28 Достаточное условие сходимости итерационного метода (теорема Самарского) 1.29 Теорема о сходимости метода Якоби 1.30 Теорема о сходимости метода простой итерации 1.31 Теорема о сходимости метода Зейделя 1.32 Скорость сходимости итерационного метода 1.33 Оценка скорости сходимости итерационного метода 1.34 Равенство Парсеваля 1.35 Оценка скорости сходимости МПИ 1.36 Теорема о сходимости ПТИМ 1.37 Теорема об оценке скорости сходимости ПТИМ 1.38 Оценка скорости сходимости для метода простой итерации 1.39 Задача на собственные значения 1.40 Степенной метод нахождения собственных значений 1.41 Условия для степенного метода 1.42 Метод обратных итераций 1.43 Метод обратных итераций со сдвигом 1.44 Что такое верхняя почти треугольная форма 1.45 Преобразование элементарных отражений (преобразование Хаусхолдера) 1.46 QR-алгоритм решения полной проблемы собственных значений 1.47 Количество действий для работы QR-алгоритма 1.48 Теорема о сохранении ВПТФ 2 Глава 2 2.1 Задача интерполяции 2.2 Интерполяционный полином 2.3 Существование и единственность интерполяционного полинома 2.4 Интерполяционный полином в форме Лагранжа 2.5 Определение погрешности интерполяционного полинома 2.6 Разделённая разность 2.7 Выражение разделённой разности через значения функции в точках 2.8 Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка 2.9 Интерполяционная функция в форме Ньютона 2.10 Погрешность интерполяционной формулы Ньютона 2.11 Интерполяционная формула Эрмита 2.12 Общий вид полинома Эрмита 2.13 H3(x) 2.14 Погрешность полинома Эрмита 2.15 Формула Симпсона 2.16 Оценка погрешности формулы Симпсона 2.17 L2 для функций 2.18 Наилучшее среднеквадратичное приближение 2.19 Отклонение 3 Глава 3 3.1 Нелинейная система 3.2 Задачи связанные с решением нелинейных уравнений и систем 3.3 Метод бисекции решения нелинейного уравнения 3.4 Метод простой итерации (МПИ) 3.5 Условие наличия корня в отрезке при использовании МПИ 3.6 Специальный вид МПИ 3.7 Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии 3.8 Метод Эйткена 3.9 Метод Ньютона (касательных) 3.10 Модифицированный метод Ньютона 3.11 Метод Ньютона для системы из 2 уравнений 3.12 Метод Ньютона: общий случай для m уравнений 3.13 Метод секущей (хорд) 3.14 Комбинированный метод 3.15 Скорость сходимости метода Ньютона 3.16 Скорость сходимости модифицированного метода Ньютона

[править] Глава 1

[править] Система линейных алгебраических уравнений (СЛАУ)

Система линейных алгебраических уравнений:

• Ax = f
• A (m × m), det A ≠ 0 — решение есть, оно единственное
• x = (x₁, x₂, ... x_m)^T
• f = (f₁, f₂, ... f_m)^T

[править] Группы методов решения СЛАУ

К курсе рассматриваются две группы методов:

1. Прямые (точные) методы
2. Итерационные (приближённые) методы

[править] Прямой метод решения СЛАУ

Прямой метод решения СЛАУ — метод, который позволяет реализовать в алгоритме определённые формулы, то есть аналитическое решение.

[править] Задача на собственные значения

Задача на собственные значения — задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение.

[править] Факторизация матрицы

Факторизация матрицы — представление матрицы А в виде произведения B × C, где

B — нижнетреугольная матрица: b11 0 0 ... 0 b21 b22 0 ... 0 ... b1m b2m b3m ... bmm

C — верхнетреугольная матрица с единицами на диаонали: 1 c12 c13 ... c1m 0 1 c23 ... c2m ... 0 0 0 ... 1

[править] В каком порядке ищутся элементы матриц B и C при факторизации А = B × C

Процесс нахождения матриц B и C размерами m × m разбивается на m этапов, причём на каждом этапе сначала по формуле b_ij = a_ij − Σ_l=1^j−1 b_il×c_lj находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.

[править] Условие существования и единственности разложения А = B × C

Все главные угловые миноры A отличны от 0:

A1 = a11 ≠ 0

;

A2 = ( a11 a12 ) ≠ 0 a21 a22

;

…;

Ai = ( a11 ... a1i ) ≠ 0 ... ai1 ... aii

[править] Связь метода Гаусса с разложением A = B × C

Три этапа метода Гаусса соответствуют трём этапам факторизации:

• В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется ^(m3 − m)/₃ операций — то же количество действий требуется для нахождения матриц B и C
• Для решения уравнения By = f  требуется ^m(m + 1)/₂ действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
• Для решения уравнения Cx =  y  требуется ^m(m − 1)/₂ действий — в точности то число действий, которое требуется для обратного хода Гаусса

[править] Метод Гаусса-Жордана

Метод Гаусса-Жордана:

• Обозначим A⁻¹ = X. Тогда AX = E
• Запишем в явном виде:
• ∑_{l = 1}^ma_ilx_lj = δ_ij, i, j = 1..m
• m² неизвестных, поэтому действий m⁶
• Разумно организовав алгоритм, можно получить порядка m³ действий

[править] Метод квадратного корня (метод Холецкого)

• Решаем уравнение Ax = f
• |A| ≠ 0 (m × m)
• A = A* ⇔ a_ij = a_ji
• A = A^T — для вещественных матриц

Факторизуем матрицу A в виде A = S*DS

	s11	s12	s13	...	s1m
	0	s22	s23	...	s2m
S =	0	0	s33	..	s3m
	...
	0	0	0	...	smm

s_ii > 0, i = 2…m

D = diag (d₁₁, …, d_mm) d_ii = ±1, i = 1..m

Тогда система решается следующим образом:

• S*DSx = f
• S*Dy = f
• Sx = y

Эти две системы решаются явным образом, ибо матрицы треугольные.

[править] Достоинства и недостатки метода квадратного корня

Плюс:

• Количество действий сокращается в два раза (^m3/₆ умножений и делений + m извлечений корня)

Минусы:

• Только для эрмитовых матриц

[править] Что значит «решить СЛАУ итерационным методом»

• x_iⁿ — i-я кордината, n-я итерация
• x⁰ — начальное приближение

Далее организуется процесс так, что lim_{n → ∞}xⁿ → x, то есть, в некоторой норме |xⁿ − x| < ε, ε > 0

[править] Вопросы, рассматриваемые при исследовании итерационного метода

• Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
• С какой скоростью

[править] Метод Якоби

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_jⁿ − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0}
• x⁰ — задано

[править] Достоинства и недостатки метода Якоби

Плюс:

• Данный метод реализуется достаточно просто

Минус:

• Очень медленная сходимость

[править] Метод Зейделя

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_j^{n + 1} − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0} (3)
• x⁰ — задано

[править] Соотношение сложностей методов Якоби и Зейделя

По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации

[править] Двуслойная запись

Двуслойная запись — когда связываются две соседние итерации.

[править] Каноническая форма записи двуслойного итерационного метода решения СЛАУ

Определение. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m × m), det A ≠ 0 называется его запись в виде:

• B_{n + 1} ^{(xn + 1 − xn)}/_{τn + 1} + Axⁿ = f (4)

где

• τ_{n + 1} > 0, n ∈ ℕ ∪ {0}
• x⁰ — задано
• ∃B_{n + 1}⁻¹

[править] Виды итерационных методов

• Метод явный, если B_{n + 1} = E. Если матрица диагональная, то тоже явный.
• Метод стационарный, если
  • B_{n + 1} = B
  • τ_{n + 1} = τ

[править] Метод простой итерации

Метод простой итерации (МПИ):

• (МПИ) (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, x⁰ — задано, n ∈ ℕ ∪ {0}, τ > 0
• Если τ меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.

[править] Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)

• A = R₁ + R₂, где R₁ — нижнетреугольная матрица с диагональными элементам r_1ii = a_ii/2, R₂ — верхнетреугольная матрица с диагональными элементам r_2ii = a_ii/2.
• (E + ωR₁)(E + ωR₂)((x^{n + 1} − xⁿ)/τ) + Axⁿ = f (5)
  • n ∈ ℕ ∪ {0}, x⁰ задано, ω > 0, τ > 0
• Применительно к канонической записи B = (E + ωR₁)(E + ωR₂)

[править] Невязка

rⁿ = f − Axⁿ

[править] Энергетическая норма

Энергетическая норма ||x||_D = (Dx,x)^1/₂, где D — положительно определённый опрератор, то есть (Dx, x) > 0, ∀ x ≠ 0.

[править] Вектор погрешности

Вектор погрешности: vⁿ = xⁿ − x.

[править] Матрица перехода

S = E − τB⁻¹A

Вывод:

• Ax = f
• ∃ A⁻¹ (m × m)
• B ^{(xn + 1 − xn)}/_τ + Axⁿ = f
• xⁿ = vⁿ + x
• B (v^n + 1 − vⁿ)/τ + Avⁿ = 0
• (v^n + 1 − vⁿ)/τ + B⁻¹Avⁿ = 0
• vⁿ⁺¹ = vⁿ − τB⁻¹Avⁿ = (E − τB⁻¹A)vⁿ
• S = E − τB⁻¹A

[править] Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода

Теорема 1. Итерационный метод B ^{(xn + 1 − xn)}/_τ + Axⁿ = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E − τB⁻¹A по модулю меньше 1: |λ_k^S| < 1.

Это означает, что оператор S — сжимающий.

[править] Достаточное условие сходимости итерационного метода (теорема Самарского)

Теорема (Самарского, о достаточном условии сходимости метода B ^{(xn + 1 − xn)}/_τ + Axⁿ = f). Пусть есть A = A* = A^T > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||xⁿ − x|| = (∑_{i = 1}^m (x_iⁿ − xi)²)^1/₂ → 0, n → ∞.

[править] Теорема о сходимости метода Якоби

Следствие 1 теоремы Самарского. Пусть ∃ A = A* > 0, 2D > A. Тогда Методя Якоби сходится при любом начальном приближении.

[править] Теорема о сходимости метода простой итерации

Следствие 3 теоремы Самарского. Пусть ∃ A = A* > 0, γ₂ = max_{1 ≤ x ≤ m}λ_k^A > 0. Тогда 0 < τ < 2/γ₂ МПИ сходится при ∀ x⁰

[править] Теорема о сходимости метода Зейделя

Следствие 4. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме. Вообще достаточно только самосопряженности оператора А: A = A* > 0

[править] Скорость сходимости итерационного метода

ln ¹/_ρ — скорость сходимости итерационного метода

[править] Оценка скорости сходимости итерационного метода

Теорема (об оценке скорости сходимости итерационного метода). Пусть

• A = A* > 0
• B = B* > 0
• 0 < ρ < 1
• ^{1 − ρ}/_τB ≤ A ≤ ^{1 + ρ}/_τB

Тогда итерационный метод B ^{(xn + 1 − xn)}/_τ + Axⁿ = f сходится к решению СЛАУ Ax = f и имеет место оценка ||v^{n + 1}||_B ≤ ρ||vⁿ||

[править] Равенство Парсеваля

Равенство Парсеваля Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑_k = 1^mc_ke_k.

Тогда равенство Парсиваля есть ||x||² = ∑_k = 1^mc_k²

[править] Оценка скорости сходимости МПИ

Следствие 2 из теоремы об оценке скорости сходимости итерационного метода. Пусть A = A* > 0,

• γ₁ = min_{1 ≤ k ≤ m} λ_k^A, > 0 в силу положительной определённости
• γ₂ = max_{1 ≤ k ≤ m} λ_k^A

Тогда МПИ (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, где τ = ²/_{γ1 + γ2}, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2 — сходится, имеет место оценка ||xⁿ⁺¹ − x|| ≤ ρ||xⁿ − x||

[править] Теорема о сходимости ПТИМ

Теорема (о сходимости ПТИМ). Пусть A = A* > 0, ω > ^τ/₄. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.

[править] Теорема об оценке скорости сходимости ПТИМ

Теорема (об оценке скорости сходимости ПТИМ). Пусть A = A* > 0. Пусть существуют такие две константы δ > 0, Δ > 0:

• A ≥ δE, R₂*R₂ ≤ ^Δ/₄ A (2)
• Положим ω = ²/_√δΔ, τ = ²/_{γ1 + γ2}, γ₁ = ^√δ/₂ (^√δΔ/_√δ+√Δ); γ₂ = ^√δΔ/₄
• ||x^{n + 1} − x||_B ≤ ρ ||xⁿ − x||_B
• где B = (E + ωR₂*)(E + ωR₂), ρ = ^{1 − √η}/_{1 + 3√η}, η = ^δ/_Δ
  • R₂* = R₁

[править] Оценка скорости сходимости для метода простой итерации

• ||x^{n + 1} − x|| ≤ ρ ||xⁿ − x||, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2, ξ = η = O(m⁻²)
• 1/ρ = ^{1 + η}/_{1 − η} ≈ (1 + η)² ≈ 1 + 2η
• ln ¹/_ρ ≈ η, n₀(ε) = O(m²)

[править] Задача на собственные значения

Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)

• λ — собственные значения
• x — собственные вектора

Два круга проблем:

• Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
• Полная проблема собственных значений — нужно находить все собственные значения

Всего m значений (с учётом кратности): λ_k, k = 1..m

Вообще говоря, собственные значения комплексные.

Все методы итерационные. Один из самых простых методов — степенной метод.

[править] Степенной метод нахождения собственных значений

Степенной метод — метод, который описывается уравнением 1:

• x_{n + 1} = Ax_n (1)
• n = 0, 1, ..., x₀ — начальное приближение
• x_n = A_nx₀

[править] Условия для степенного метода

• Предположения относительно матрицы A:
  • Все собственные значения расположены в порядке неубывания модуля: |λ₁| ≤ |λ₂| ≤ |λ₃| ≤ ... ≤ |λ_m|
  • Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e_k}₁^m — базис из собственных векторов A (Ae_k = λ_ke_k, k = 1..m)
  • Ограничение B: последнее собственное значение не является кратным: |(λ_{m − 1})/(λ_m) < 1
  • Ограничение C: ∀ x = c₁e₁ + ... + c_me_m, c_m ≠ 0

[править] Метод обратных итераций

1. ∃ A⁻¹. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
   • Ax_{n + 1} = x_n, n = 0, 1, …, x₀ — начальное приближение (3) Этот метод неявный. Перепишем его как:
   • x_{n + 1} = A⁻¹x_n (4)
   • x_n = (A⁻¹)ⁿx_n

Условия:
A) ∃ {e_k}₁^m из СВ
B) |λ₁/λ₂| < 1
C) x₀ = c₁e₁+ … + c_me_m, c₁ ≠ 0

Тогда:

• x_n = c₁λ₁⁻ⁿe₁+ … + c_mλ_m⁻ⁿe_m
• x_n/e₁λ₁⁻ⁿ = e₁ + … + (c_m/c₁)(λ₁/λ_m)ⁿe_m

[править] Метод обратных итераций со сдвигом

• (A − αE)x_{n + 1} = x_n (5)
  • n = 0, 1, …, x₀ — начальное приближение, α ∈ R
• ∃ (A − αE)⁻¹
• x_{n + 1} = (A − αE)⁻¹x_n
• x_n = e_l
• 1/|λ_l − α| = max_{1 ≤ k ≤ m} 1/|λ_k − α|

[править] Что такое верхняя почти треугольная форма

Верхняя почти треугольная форма — форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.

[править] Преобразование элементарных отражений (преобразование Хаусхолдера)

Определение. Преобразование элементарных отражений (Преобразование Хаусхолдера). Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vv^T/||v||²

[править] QR-алгоритм решения полной проблемы собственных значений

∀ A = Q × R, Q⁻¹ = Q^T, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.

[править] Количество действий для работы QR-алгоритма

• полная — O(m³)
• ВПТФ — O(m²)
• А - трехдиагональная - O(m)

[править] Теорема о сохранении ВПТФ

Пусть C = B × A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.

[править] Глава 2

[править] Задача интерполяции

Суть задачи: есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x₀ < x₁ < x₂ < … < x_n ≤ b — {x_i}₀ⁿ — узлы интерполирование (n + 1 штук). Есть f(x_i) = f_i, i = 0…n. Если полином P_n(x) = a₀ + a₁x + … a_nxⁿ такой, что P_n(x_i) = f(x_i), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).

[править] Интерполяционный полином

Если полином P_n(x) = a₀ + a₁x + … a_nxⁿ такой, что P_n(x_i) = f(x_i), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).

[править] Существование и единственность интерполяционного полинома

При условиях, накладываемых в постановке задачи интерполяции (узлы интерполирования не совпадают) интерполяционный полином существует и единственный.

[править] Интерполяционный полином в форме Лагранжа

L_n(x) = ∑_{k = 0}ⁿ(ω(x))/((x −x_k)ω'(x_k)) × f(x_k), где

• ω(x) = (x − x₀)(x − x₁)…(x − x_n) = ∏_{i = 0}ⁿ(x_i − x_j)
• ω(x) = [ ](x − x_k)
• ω'(x) = [ ] + [ ]'(x − x_k)
• ω'(x_k) = ∏_{k ≠ j}ⁿ(x_k − x_j)

[править] Определение погрешности интерполяционного полинома

Погрешность интерполяционной формулы Лагранжа ψ_Ln(x) = f(x) − L_n(x). Во всех узлах она будет совпадать: ψ_Ln(x_i) = 0.

Замечание 1. Если f(x) — полином степени ≤ n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.

Замечание 2. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.

[править] Разделённая разность

Разделённой разностью первого порядка, построенной по узлам x_i, x_j называется отношение f(x_i, x_j) = (f(x_j) − f(x_i)/(x_j − x_i))

Разделённая разность k+1-го порядка: пусть есть f(x_j, x_{j + 1}, …, x_{j + k}), f(x_{j + 1}, x_{j + 2}, …, x_{j + k + 1}) — разности k-го порядка. Тогда f(x_j, x_{j + 1}, …, x_{j + k + 1}) = (f(x_{j + 1}, x_{j + 2}, …, x_{j + k + 1}) − f(x_j, x_{j + 1}, …, x_{j + k}))/(x_{j + k + 1} − x_j) — разделённая разность k + 1-го порядка.

[править] Выражение разделённой разности через значения функции в точках

Разделённая разность k-го порядка, построенная по узлам x₀, … x_k может быть записана как f(x₀, x₁, …, x_k) = ∑_{i = 0}^k(f(x_i))/(ω_{0, k}'(x_i))

[править] Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка

f(x_k) = f(x₀) + (x_k − x₀)f(x₀, x₁) + (x_k − x₀)(x_k − x₁)f(x₀, x₁, x₂) + … + (x_k − x₀)(x_k − x₁)…(x_k − x_{k − 1})f(x₀, x₁, …, x_k)

[править] Интерполяционная функция в форме Ньютона

N_n(x) = f(x₀) + (x − x₀)f(x₀, x₁) + (x − x₀)(x − x₁)f(x₀, x₁, x₂) + … + (x − x₀)(x − x₁)…(x − x_{n − 1})f(x₀, x₁, …, x_n)

[править] Погрешность интерполяционной формулы Ньютона

Погрешность та же самая, но записана внешне по-другому:

|ψ_Nn(x)| = |f(x) − N_n(x)| ≤ M_{n + 1}/(n + 1)! × |ω(x)|, M_{n + 1} = sup_{a ≤ x≤ b} |f(x)^{(n + 1)}|

== Когда лучше использовать Ньютона, а когда — Лагранжа

• Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
• Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах

[править] Интерполяционная формула Эрмита

Пусть у нас есть узлы x₀, … x_m — 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)

• a_i ∈ N ( натуральное), i = 0…m
• a_i — кратность i-го узла

Цель: построить H_n(x)

Замечание. H_n⁽ⁱ⁾ = f⁽ⁱ⁾(x_k), k = 0…m, i = 0…a_k − 1 (1)

При выполнении условия a₀ + a₁ + … + a_m = n + 1 мы можем построить полином Эрмита, причём единственный.

[править] Общий вид полинома Эрмита

H_n(x) = ∑_{k = 0}^m ∑_{i = 0}^{a_k − 1} c_{k, i}(x)f⁽ⁱ⁾(x_k)

• c_{k, i}(x) — полином n-й степени
• x_i — различные

[править] H₃(x)

H₃(x) = c₀(x)f(x₀) + c₁(x)f(x₁) + c₂(x)f(x₂) + b₁(x)f'(x₁)

• c₀(x) = ((x − x₁)²(x − x₂))/((x₀ − x₁)²(x₀ − x₂))
• c₂(x) = ((x − x₁)²(x − x₀))/((x₂ − x₁)²(x₂ − x₀))
• b₁(x) = ((x − x₀)(x − x₁)(x − x₂))/((x₁ − x₀)(x₁ − x₂))
• c₁(x) = (x − x₀)(x − x₂)/((x₁ − x₀)²(x₁ − x₂)²)) × [1 − ((x − x₁)(2x₁ − x₀ − x₂))/((x₁ − x₀)(x₁ − x₂))]

[править] Погрешность полинома Эрмита

• ψ_H3(x) = f(x) − H₃(x) = f⁽⁴⁾(ξ)/4!
• M₄ = sup_{x0 ≤ x ≤ x2} |f⁽⁴⁾(x)|
• |f(x) − H₃(x)| ≤ M₄/4! × |ω(x)|

[править] Формула Симпсона

Пусть требуется найти ∫_a^b f(x)dx, f(x_i) = f_i, f(x_i+0,5h) = f_{i + 1/2}

По формуле Симпсона:

• ∫_{xi − 1}^x_i f(x)dx ≈ h/6 × (f_{i − 1} + 4f_{i − 1/2} + f_i)

[править] Оценка погрешности формулы Симпсона

• M₄ = sup_{a ≤ x ≤ b} |f⁽⁴⁾(x)|
• Ψ_h(f) ≤ (h/2)⁴ (M₄(b − a))/180 = O(h⁴)

[править] L₂ для функций

Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫_a^b f²(x)dx < ∞, f ∈ L₂. В этом функциональном пространстве вводим векторное произведение: ∀ f, g ∈ L₂: (f, g) = ∫_a^b f(x)g(x)dx. Норма: ||f|| = (f, f)^1/2 = (∫_a^b f²(x)dx)^1/2. Эта норма не согласована с нормой в дискретном L₂.

[править] Наилучшее среднеквадратичное приближение

• Требуется найти такой обобщённый многочлен φ(x) = ∑_{k = 0}ⁿ c__kφ_k(x), что
  • ||f − φ(x)|| = ∫_a^b (f(x) − φ(x))²dx = min_φ(x)||f − φ(x)||_L2²

[править] Отклонение

∫_a^b (f(x) − ∑_{k = 0}ⁿ c_kφ_k(x))²dx = ∫_a^b f(x)²dx − 2∑_{k = 0}ⁿ c_k ∫_a^b f(x)φ₀(x)dx + ∑_{l = 0}ⁿ c_l ∑_{k = 0}ⁿ c_k ∫_a^b φ₀²(x)dx = ∫_a^b f(x)²dx − ∑_{k = 0}ⁿ c_k² ≥ 0

• ∑_{k = 0}ⁿ c_k² ≤ ||f||² — неравенство Бесселя
• ∑_{k = 0}ⁿ c_k² = ||f||² — равенство Парсеваля

[править] Глава 3

[править] Нелинейная система

{	f1(x1, x2, …, xm) = 0
	f2(x1, x2, …, xm) = 0
	…
	fm(x1, x2, …, xm) = 0

• f: R_m → R_m
• f_ = (f₁, …, f_m)^T
• x_ = (x₁, …, x_m)^T
• f_ (x_) = 0

[править] Задачи связанные с решением нелинейных уравнений и систем

1. Локализация корня x_*, f(x_*) = 0, указать область, где он находится. Этим мы заниматься не будем
2. Строится итерационный процесс, и аккуратно выбирая начальное приближение x₀ из локализованной области, x_n → x_*, n → ∞

[править] Метод бисекции решения нелинейного уравнения

Второй метод более регулярный и он называется метод бисекции.

• f(a) < 0
• f(b) > 0
• Берётся x₀ = (a + b)/2
• Если f(x₀) > 0, то x_* ∈ (a, x₀)

Каждый раз мы сужаем в два раза промежуток, где находится корень

[править] Метод простой итерации (МПИ)

• f(x) = 0 (1)
• x_* ∈ U_a(x_*) (по определению)
• x = S(x) (2)
• x_{n + 1} = S(x_n) (3)
• x₀ ∈(x_*)

S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ U_a(x_*).

[править] Условие наличия корня в отрезке при использовании МПИ

Если известно, что ∃ S'(x), и sup_{x ∈ Ua(x*)} |S'(x)| = q < 1, то МПИ сходится, x₀ ∈ U_a(x_*)

[править] Специальный вид МПИ

(x_{n + 1} − x_n)/τ + f(x_n) = 0, τ > 0, x₀ ∈ U_a(x_*), n = 0, 1, 2, …

[править] Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии

−1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M₁

[править] Метод Эйткена

Предположим, что x_n − x_* = Aqⁿ (6). Запишем три итерации:

• x_{n − 1} − x_* = Aq^{n − 1} (7)
• x_n − x_* = Aqⁿ (8)
• x_{n + 1} − x_* = Aq^{n +1} (9)

Тогда:

• x_* = x_n − ((x_{n + 1} − x_n)²)/(x_{n + 1} − 2x_n + x_{n − 1})

Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.

[править] Метод Ньютона (касательных)

• f(x) = 0
• x_* ∈ U_a(x_*) (по определению)
• xⁿ — n-я итерация
• x^{n + 1} = xⁿ − f(xⁿ)/f'(xⁿ), n = 0, 1, …, x⁰ — начальное приближение (2)
• От функции требуется гладкость до третьей производной

Метод Ньютона очень быстро сходится, но он может зацикливаться.

[править] Модифицированный метод Ньютона

• x^{n + 1} = xⁿ − f(xⁿ)/f'(x⁰), n = 0, 1, …, x⁰ — начальная итерация
• Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания

[править] Метод Ньютона для системы из 2 уравнений

{	f1(x1, x2) = 0	(3)
	f2(x1, x2) = 0

(x₁^*, x₂^*) — решение

J(x) = (	(δf1/δx1)(x1n, x2n)	(δf1/δx2)(x1n, x2n)	)
	(δf2/δx1)(x1n, x2n)	(δf2/δx2)(x1n, x2n)

• ∃ J⁻¹(xⁿ)
• x^{n + 1} = xⁿ − J⁻¹(xⁿ)f(xⁿ), n = 0, 1, …, x⁰ ∈ U_a(x^*)

[править] Метод Ньютона: общий случай для m уравнений

{	f1(x1, x2, …, xm) = 0	(6)
	f2(x1, x2, …, xm) = 0
	…
	fm(x1, x2, …, xm) = 0

• (J(x))_ij = (δf_i/δx_j), i, j = 1…m
• x^{n + 1} = xⁿ − J⁻¹(xⁿ)f(xⁿ), n = 0, 1, …, x⁰ ∈ U_a(x^*) (6)
• x^{n + 1} = xⁿ − J(x⁰)f(xⁿ)

[править] Метод секущей (хорд)

• x^{n + 1} = xⁿ − f(xⁿ)/f'(x⁰), n = 0, 1, …
• f'(xⁿ) = (f(x^{n + 1}) − f(xⁿ))/(x^{n + 1} − xⁿ)

[править] Комбинированный метод

Подставим в метод Ньютона приближение производной:

• x^{n + 1} = xⁿ − (xⁿ − x^{n − 1})f(xⁿ)/(f(xⁿ) − f(x^{n − 1}))

[править] Скорость сходимости метода Ньютона

• Z_n = xⁿ − x_* — погрешность
• ∃ M > 0: 0,5|S''(x~_n)| ≤ M
• |Z_n| ≤ (M|Z₀|)²ⁿ/M = 1/M × q²ⁿ

[править] Скорость сходимости модифицированного метода Ньютона

• S'(x) = 1 − f'(x)/f'(x⁰)
• S'(x_*) = 1 − f'(x_*)/f'(x₀)

Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.