Численные Методы, Определения

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

(Различия между версиями)
Перейти к: навигация, поиск
(Что значит «решить СЛАУ итерационным методом»)
(Соотношение сложностей методов Якоби и Зейделя)
 
(5 промежуточных версий не показаны.)
Строка 197: Строка 197:
== Соотношение сложностей методов Якоби и Зейделя ==
== Соотношение сложностей методов Якоби и Зейделя ==
-
По сложности и скорости сходимости эти два метода одинаковы.
+
По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации
== Двуслойная запись ==
== Двуслойная запись ==
Строка 285: Строка 285:
== Оценка скорости сходимости МПИ ==
== Оценка скорости сходимости МПИ ==
-
'''Следствие 2 из теоремы об оценке скорости сходимости итерационного метода.''' Пусть A = a* > 0,
+
'''Следствие 2 из теоремы об оценке скорости сходимости итерационного метода.''' Пусть A = A* > 0,
* &gamma;<sub>1</sub> = min<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>, > 0 в силу положительной определённости
* &gamma;<sub>1</sub> = min<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>, > 0 в силу положительной определённости
* &gamma;<sub>2</sub> = max<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>
* &gamma;<sub>2</sub> = max<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>
-
Тогда МПИ (x<sup>n+1</sup> &minus; x<sup>n</sup>)/&tau; + Ax<sup>n</sup> = f, где &tau; = <sup>2</sup>/<sub>&gamma;<sub>1</sub> + &gamma;<sub>2</sub></sub>, &rho; = <sup>1 &minus; &xi;</sup>/<sub>1 + &xi;</sub>, &xi; = <sup>&gamma;<sub>1</sub></sup>/<sub>&gamma;<sub>2</sub></sub> — сходится, имеет место оценка ||x<sup>n</sup> &minus; x|| &le; &rho;||x<sup>n</sup> &minus; x||
+
Тогда МПИ (x<sup>n+1</sup> &minus; x<sup>n</sup>)/&tau; + Ax<sup>n</sup> = f, где &tau; = <sup>2</sup>/<sub>&gamma;<sub>1</sub> + &gamma;<sub>2</sub></sub>, &rho; = <sup>1 &minus; &xi;</sup>/<sub>1 + &xi;</sub>, &xi; = <sup>&gamma;<sub>1</sub></sup>/<sub>&gamma;<sub>2</sub></sub> — сходится, имеет место оценка ||x<sup>n+1</sup> &minus; x|| &le; &rho;||x<sup>n</sup> &minus; x||
== Теорема о сходимости ПТИМ ==
== Теорема о сходимости ПТИМ ==
Строка 350: Строка 350:
* x<sub>n</sub>/e<sub>1</sub>&lambda;<sub>1</sub><sup>&minus;n</sup> = e<sub>1</sub> + &hellip; + (c<sub>m</sub>/c<sub>1</sub>)(&lambda;<sub>1</sub>/&lambda;<sub>m</sub>)<sup>n</sup>e<sub>m</sub>
* x<sub>n</sub>/e<sub>1</sub>&lambda;<sub>1</sub><sup>&minus;n</sup> = e<sub>1</sub> + &hellip; + (c<sub>m</sub>/c<sub>1</sub>)(&lambda;<sub>1</sub>/&lambda;<sub>m</sub>)<sup>n</sup>e<sub>m</sub>
-
== Метод обратных итераций со сдигом ==
+
== Метод обратных итераций со сдвигом ==
* (A &minus; &alpha;E)x<sub>n + 1</sub> = x<sub>n</sub> (5)
* (A &minus; &alpha;E)x<sub>n + 1</sub> = x<sub>n</sub> (5)
** n = 0, 1, &hellip;, x<sub>0</sub> — начальное приближение, &alpha; &isin; R
** n = 0, 1, &hellip;, x<sub>0</sub> — начальное приближение, &alpha; &isin; R
Строка 416: Строка 416:
N<sub>n</sub>(x) = f(x<sub>0</sub>) + (x &minus; x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + &hellip; + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)&hellip;(x &minus; x<sub>n &minus; 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, &hellip;, x<sub>n</sub>)
N<sub>n</sub>(x) = f(x<sub>0</sub>) + (x &minus; x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + &hellip; + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)&hellip;(x &minus; x<sub>n &minus; 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, &hellip;, x<sub>n</sub>)
-
== Погрешность инторполяционной формулы Ньютона ==
+
== Погрешность интерполяционной формулы Ньютона ==
Погрешность та же самая, но записана внешне по-другому:
Погрешность та же самая, но записана внешне по-другому:
Строка 422: Строка 422:
== Когда лучше использовать Ньютона, а когда — Лагранжа
== Когда лучше использовать Ньютона, а когда — Лагранжа
-
* Ньютон удобен при постепенном добавлении узлов, когда их количество нефисировано
+
* Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
* Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах
* Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах

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

Содержание

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

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

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

  • Ax = f
  • A (m × m), det A ≠ 0 — решение есть, оно единственное
  • x = (x1, x2, ... xm)T
  • f = (f1, f2, ... fm)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 этапов, причём на каждом этапе сначала по формуле bij = aij − Σl=1j−1 bil×clj находится элемент матрицы 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)/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

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

  1. ∃ A−1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
    • Axn + 1 = xn, n = 0, 1, …, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
    • xn + 1 = A−1xn (4)
    • xn = (A−1)nxn

Условия:
A) ∃ {ek}1m из СВ
B) |λ12| < 1
C) x0 = c1e1+ … + cmem, c1 ≠ 0

Тогда:

  • xn = c1λ1−ne1+ … + cmλm−nem
  • xn/e1λ1−n = e1 + … + (cm/c1)(λ1m)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 = 0mi = 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 ckab f(x)φ0(x)dx + ∑l = 0n clk = 0n ckab φ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

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

  1. Локализация корня x*, f(x*) = 0, указать область, где он находится. Этим мы заниматься не будем
  2. Строится итерационный процесс, и аккуратно выбирая начальное приближение 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)

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


Численные Методы


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22


Календарь

Февраль
пн
12 19
вт
13 20 27
Март
пн
05 12 19 26
вт
06 13 20 27
Апрель
пн
02 09 16 23 29
вт
03 10 17 24

Дополнительная информация

Содержание курса | Задачи на лекциях

Материалы к экзамену

Вопросы по курсу | Определения

Личные инструменты
Разделы