Численные Методы, 03 лекция (от 19 февраля)

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

Перейти к: навигация, поиск

Предыдущая лекция | Следующая лекция

Содержание

[править] Глава 1. Численные методы линейной алгебры

[править] Параграф 4. Метод квадратного корня (продолжение)

Мы рассматриваем задачу

  • Ax = f (1)
  • A имеет размер m × m
  • |A| ≠ 0
  • A = A* ⇔ aij = aji
  • A = S*DS, sij > 0 (2)

(DS)ij — элемент, стоящий в j-м столбце i-й строке,

  • (DS)ij = ∑l = 1mdilslj
  • (S*DS)ij = ∑l = 1mslidllslj = ∑l = 1i − 1slidllslj + siidiisii + ∑l = i + 1mslidllslj = aij

Рассмотрим sli: sli = 0, l > i ⇒ 3-е слагаемое равно 0.

  • siidiisii = aij − ∑l = 1i − 1slidllslj, i ≤ j (*)

Рассмотрим это соотношение при i = j

  • ss = |s|2
  • sii = aii − ∑l = 1i − 1slislidll
  • dii = sign(aii − ∑l = 1i − 1|sli|2dll) (4)
  • sii = √aii − ∑l = 1i − 1|sli|2dll) (5)

из (*): sij = aij − ∑l = 1i − 1slislidll/siidii, i < j (6)

Пока миноры ненулевые, разложение существует и единственно.

Для чего применяется данный алгоритм:

Факторизируем матрицу A и подставляем в уравнение:

S*DS = f

Оно сводится к двум системам, имеющие верхнетреугольный/нижнетреугольный вид и явно находящиеся решения:

  • SDy = f (7)
  • Sx = y (8)

Сложность — порядка m3/6 умножений и делений + m извлечений корня.

Плюс:

  • Количество действий сокращается в два раза

Минусы:

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

Под прямыми методами можем подвести черту.

Теперь встаёт вопрос: если мы можем решать методом Гаусса, то зачем нужны другие методы решения?

  1. Точное решение всё равно не получить, ибо погрешности
  2. Правые части обычно задаются приближённо и тогда непонятно, зачем точный метод, когда решение всё равно будет приближённое

[править] Параграф 5. Примеры и канонический вид итерационных методов решения систем линейных алгебраических уравнений

Задача:

  • Ax = f (1)
  • A имеет размер m × m
  • |A| ≠ 0

Что значит «решение итерационным методом»?

Обозначим:

  • xin — i-я ккордината, n-я итерация
  • x0 — начальное приближение

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

  • n0(ε) — количество итераций. Эффективность алгоритма оценивается именно по нему. Например, метод Самарского сходится на порядок быстрее других.

Два вопроса, которые рассматриваются при исследовании итерационного метода?

  • Будет ли сходиться
  • С какой скоростью

Запишем уравнение (1) следующим образом:

j = 1maijxj = fi, i = 1, m

Запишем в виде:

j = 1i − 1aij + aiixi + ∑j = i + 1maijxj = fi

Пусть aii ≠ 0, xi = fi/aii − ∑j = 1i − 1 aij/aiixj − ∑j = i + 1m aij/aiixj (2)

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

Навешиваем слева (n + 1)-ю итерацию, а справа — n-ю:

  • 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 — задано
  • x1n + 1 = f1/a11 − ∑j = 2m a1j/a11xjn
  • x2n + 1 = f2/a22a21/a22x1n + 1 − ∑j = 3m a1j/a22xjn

Продвигаясь по координате i мы получаем все координаты.

По сложности и сходимости эти два метода одинаковы

R1 = ( 0 0 )
aij 0
P = ( a11 0 )
0 amm
R2 = ( 0 aij )
0 0


Ясно, что ∀ A = R1 + D + R2

  • R1x + Dx + R2x = f
  • Dx = f − R1x − R2x
  • x = D−1f − D−1R1x − D−1R2x

В таком случае метод Якоби записывается следующим способом: xn + 1 = D−1f − D−1R1xn − D−1R2xn, n ∈ ℕ ∪ {0}, x0 задано

метод Зейдаля: xn + 1 = D−1f − D−1R1xn + 1 − D−1R2xn, n ∈ ℕ ∪ {0}, x0 задано

Когда существует D−1? когда aii ≠ 0

  • (МЯ) Dxn + 1 = f − R1xn − R2xn
  • (МЗ) (D + R1)xn + 1 = f − R2xn
  • (МЯ) D(xn + 1 − xn) + ARxn = f
  • (МЗ) (D + R1)(xn + 1 − xn) + Axn = f

Из-за разной записи в результате решили прийти к канонической форме. И это ввёл Самарский. Что позволило создать стройную теорию. В последней записи она информативнее.

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

Можно строить многошаговые методы.

Определение. Канонической формой записи двуслойного итерационного метода решения системы (1) называется его запись в виде:

  • 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 — нижнетреугольная матрица с половиной диагоналиьных элементов, R2 — верхнетреугольная матрица с половиной диагональных элементов
    • (E + ωR1)(E + ωR2)((xn + 1 − xn)/τ) + Axn = f (5)
      • n ∈ ℕ ∪ {0}, x0 задано, ω > 0, τ > 0
    • Будем говорить хвалебные слова в адрес ПТИМ
    • В данном случае B = (E + ωR1)(E + ωR2)
То, что метод неявный, стало явно видно

[править] Реализация ПТИМ

Обозначим Wn + 1 = (E + ωR2)((xn + 1 − xn)/τ)

Невязка: rn = f − Axn

Тогда мы можем переписать ПТИМ следующим образом:

(E + ωR1)Wn + 1 = rn (6)

Введём вектор vn + 1 = ((xn + 1 − xn)/τ)

Тогда (E + ωR1)vn + 1 = Wn + 1 (7)

xn + 1 = xn + τvn + 1 (8)

[править] Параграф 6. Теоремы о сходимости итерационных методов

  • Ax = f (1)
  • |A| ≠ 0, (m × m)

По-прежнему решаем систему (1) итерационными методами:

  • B (xn + 1 − xn)/τ + Axn = f (2)
    • τn + 1 > 0
    • n ∈ ℕ ∪ {0}
    • x0 задано
    • ∃A−1, B−1

Введём m-мерное пространство :

  • ∀ x ∈ H
    • dim H = m
    • x = (x1, x2, ..., xm)
    • ∀ x, y ∈ H (x, y) = ∑i = 1mxiyi
    • ||x|| = (x, x)1/2 = (∑i = 1m xi2)1/2


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


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

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

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

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

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


Эта статья является конспектом лекции.
Личные инструменты
Разделы