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

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

Версия от 08:44, 21 июня 2007; Esyr01 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение)

Решение нелинейной системы (3), (4), полученной на предыдущей лекции.

  • cij = (aij − Σl=1i−1 bil×clj)/bii, i < j ... (3)
  • bij = aij − Σl=1j−1 bil×clj, i ≥ j ... (4)

Первый шаг: первая строка C

  • b11 = a11
  • c1j = a1j/b11, j = 1…m

Второй шаг: первый столбец B

  • bi1 = ai1, i = 1…m

Третий шаг: вторая строка C

  • b22 = a22 − b21 × c12
  • c2j = (a2j − b21×c1j)/b22, j = 2…m

Четвёртый шаг: второй столбец B

  • bi2 = ai2 − bi1×c12, i = 2…m

Таким образом, мы решили нелинейную систему, грамотно организовав алгоритм.

Факторизация A = B × C (2) осуществляется при bii ≠ 0

Утверждение. Пусть все главные угловые миноры A отличны от 0:

A1 = a11 ≠ 0 ;
A2 = ( a11 a12 ) ≠ 0
a21 a22
; …;
Ai = ( a11 ... a1i ) ≠ 0
...
ai1 ... aii

Тогда разложение матрицы (2) существует и единственно.

Класс задач, где присутствуют симметрические матрицы, достаточно широк

Доказательство.

∃! Ai = Bi Ci = b11 × b22 × … × bi − 1,i − 1 × bii

b11 × b22 × … × bi − 1,i − 1 = Ai − 1

bii = Ai/Ai − 1, i = , i = 2…m

ч. т. д.

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

В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется (m3 − m)/3 операций.

Задача. Показать, что для реализации (вычисления) по формулам (3), (4) требуется точно такое же число действий: (m3 − m)/3 (решение).

В результате факторизации получаем систему BСx = f. Система Ax = f (1) сводится к решению двух уравнений By = f (5), Cx =  y (6)

Число действий для решения (5):
bi1y1 + bi2y2 + … + biiyi = fi, i = 1..m
yi = (fi - Σl = 1i − 1bilyl)/bii
i − 1 умножение + 1 деление — i действий
Итого Σi = 1mi = m(m+1)/2 действий.
В точности то же самое число действий, что требуется для вычисления правой части в методе Гаусса.

Число действий для решения (6):
xi + Ci, i + 1xi+1 + … + Cimxm = yi, i = 1..m
xi = yi − Σl = i + 1mcilxl
m − i умножений, i = 2…m
Итого m(m − 1)/2
В точности то число действий, которое требуется для обратного хода Гаусса.

Весь метод Гаусса требует (m3 − m)/3 + m2 = m/3 × (m2 + 3m − 1). В чём же выигрыш? Он будет показан при нахождении обратной матрицы.

Параграф 3. Обращение матрицы методом Гаусса-Жордана

Пусть есть матрица A размера m × m, det A ≠ 0. Тогда для неё существует A−1: A−1 × A = A × A−1 = E.

Один из способов нахождения матрицы — нахождение алгебраических дополнений. Один из недостатков в том, что при малом определителе гигантские погрешности. Второй способ в приписывании единичной матрицы и проведения над ней действий трёх видов до получения единичной матрицы слева. Тоже не лучше.

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

  • Обозначим A−1 = X. Тогда AX = E
  • Запишем в явном виде:
  • l = 1mailxlj = δij, i, j = 1..m (2)
  • m2 неизвестных, поэтому действий m6

Сейчас мы покажем, что разумно организовав алгоритм, получим порядка m3 действий.

Решение этой системы распадётся на решение m систем, у которых будет меняться только правая часть.

Введём вектор x(j) = (x1j, x2j, …, xmj)T

Вектор δ(j) = (0, 0, …, 0, 1 (j-я позиция), 0, …, 0)

Тогда Ax(j) = δ(j), j = 1..m (3)

Факторизуем A = B×C. Для этого потребуется (m3 − m)/3 действий

Далее решаем 2 системы:

BCx(j) = δ(j)

Cx(j) = y(j)

  • By(j) = δ(j) (4), j = 2…m
  • Cx(j) = y(j) (5)

Решение пары таких систем требует m2 действий, а всего таких систем m. То есть, итого (m3 − m)/3 + m3 = 4/3 m3m/3

Теперь покажем, что число действий можно свести к m3. За счёт чего мы можем снизить число действий:

В уравнении (4) правые части имеют очень специальный вид. Мы в первый раз ненулевую компоненту встретим только на j-м шаге.

Первое уравнение:

  • b11y1(j) = 0 => y1(j) = 0
  • b21y1(j) + b22y2(j) = 0 ⇒ y2(j) = 0
  • yj − 1(j) = 0 (6*)
  • bjjyj(j) = 1 ⇒ yj(j) = 1/bjj
  • bijyj(j) + bi, j + 1yj + 1(j) + … +biiyi(j) = 0, i = j + 1..m
  • yi(j) = l = ji − 1bilyl(j))/bii, i = j+1..m (6)

Пусть i, j фиксированы. Тогда 1 деление и i − j умножений. Отпустим один из индексов, i. Получим:

  • m − j + (m − j − 1) + … + 2 + 1 = (m − j + 1)(m − j)/2 умножений
  • m − j делений (6) + 1 (6*)
  • m − j + 1 делений

Всего при фиксированном j: (m − j + 1)(m − j)/2 + 2(m − j + 1)/2 = (m − j + 1)(m − j + 2)/2 умножений и делений.

Отпускаем j, j = 2…m. Получим: ∑j = 1m((m − j + 1)(m − j + 2)/2) ... (δ)

Задача. Показать, что (δ) = m(m+1)(m+2)/6

Для (5) мы выигрыша получить не можем. Поэтому для (5) при фиксированном j получаем m(m − 1)/2 действий. Для решения всех систем (5) требуется m2(m− 1)/2 действий. Итого получаем:

(m3 − m)/3 + m(m + 1)(m + 2)/6 + m2(m − 1)/2 = m/6 × (2m2 − 2 + m2 + 3m + 2 + 3m2 − 3m) = m3

Таким образом, разумно организовав вычисления, мы получим обратную матрицу за m3 операций.

Параграф 4. Метод квадратного корня

Другое название: метод Холецкого

Решаем уравнение Ax = f (1)

  • |A| ≠ 0 (m × m)
  • A = A* ⇔ aij = aji
  • A = AT — для вещественных матриц

Суть метода:

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

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

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

  • S*DSx = f
  • S*Dy = f (3)
  • Sx = y

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

рассмотрим вещественную матрицу A = ((a11, a12), (a12, a22)) aij — вещественное. Тогда S = ((s11, s12), (0, s22)), S* = ((s11, 0), (s12, s22)), D=((d11, 0), (0, d22))

Умножим DS = ((d11, 0), (0, d22)) ((s11, s12), (0, s22)) = ((d11s11, d11s12), (0, d22s22)). Она сохранила верхнетреугольную форму (позже покажем, что умножение верхнетреугольной на почти верхнетреугольную сохраняет форму). Домножим на S*. S*DS = ((s11, 0), (s12, s22))((d11s11, d11s12), (0, d22s22)) = ((d11s112, d11s12s11), (d11s12s11, d11s122 + d22s222)) = A. Поэлементно приравниваем компоненты.

  • d11s112 = a11
  • d11s12s11 = a12
  • d11s122 + d22s222 = a22

Посмотрим на первое уравнение. Из него понятно, что d11 = sign a11. Тогда отсюда получаем s11 = sqrt(|a11|). Дальше смотрим на второе уравнение: s12 = a12/d11s11. Теперь последнее уравнение рассматриваем. Перепишем его в виде: d22s222 = a22 − d11s122. Отсюда получим d22 = sign(a22 − d11s122), s22 = sqrt(|a22 − d11s122|). Таким образом, мы показали, что для матрицы 2×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

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

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

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

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


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