Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

gos / шпоры / ЧМ_мал

.pdf
Скачиваний:
12
Добавлен:
27.03.2016
Размер:
297.11 Кб
Скачать

1. Метод Гаусса решения систем линейных алгебраических уравнений. Выбор главного элемента.

Метод Гаусса.

a

x

a

x

... a

x a

 

11 1 12 2

1n n

1n 1

 

 

x

a

x

... a

x

a

a

 

21 1 22 2

2n n

2 n 1

 

 

 

 

 

 

 

Решаем СЛАУ:

...

Выполняем n-1 шаг вперёд (приведение матрицы к верхнеугольной), потом n-1 шаг назад (нахождение х)

a11 (1)

1

 

 

 

 

 

 

 

 

 

 

(1)

 

 

(0)

 

 

 

 

a

 

 

 

 

 

 

 

 

 

1 j

 

 

 

 

j 2,3,..., n 1

a

 

 

 

 

 

 

 

,

 

 

(0)

 

1 j

 

 

 

 

 

 

 

 

 

 

 

 

a11

 

 

 

 

 

...

 

 

 

 

 

 

 

 

 

 

 

a(1)

a(0)

a(1)

a(0)

, i 2,.., n;

j 2,..., n 1

ij

 

 

ij

 

ij

 

 

i1

 

 

По аналогичной формуле преобразуются все нижеследующие строчки. На (n-2)-ом шаге получается треугольная матрица.

Метод Гаусса с выделением главного элемента.

1)В текущей строке находится max aij

2)Переставляются столбцы (то есть переименовываются хi в хj и наооборот), чтобы max aij оказался спереди.

Метод дает выше точность для матриц большой размерности

2. Метод простой итерации и метод Гаусса-Зейделя решения систем линейных алгебраических уравнений. Исследование сходимости.

Метод простой итерации решения СЛАУ.

Ax F,

 

A

 

0

 

 

x(0) любое

 

B E A

x(k 1) B x(k) F

Сходится, если хотя бы одна норма у B < 1 по модулю, т.е., например,

если max| | < 1.

Этот метод имеет ограниченную область сходимости.

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

(x * xk ) B(x * x(k 1) ) ... (B)k (x * x0)

B 1

для сходимости

Напишем это же самое в развёрнутом виде:

x

(k 1)

(1 a )x(k)

a

x(k)

... f

 

 

 

 

 

1

11

1

12 2

 

 

1

 

 

 

 

 

(k 1)

a x

(k)

(1 a

 

)x

(k)

a

x

(k)

... f

 

x

 

 

 

 

 

 

 

 

2

21 1

 

22

 

2

 

23

3

 

2

 

 

(k 1)

 

(k)

 

(k)

 

 

 

 

(k)

... f3

x3

a31x1

a32x2

 

 

(1

a33)x3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Метод Зейделя.

Усовершенствуем предыдущую систему:

2

x(k 1)

(1 a

 

 

)x(k) a

x(k) ... f

 

 

 

 

 

 

1

11

1

12 2

 

 

 

1

 

 

 

 

 

 

 

(k 1)

a x

(k 1)

(1 a

)x

(k)

a x

(k)

... f

 

x

 

 

 

 

 

 

 

 

 

2

21

1

 

 

22

2

 

23 3

 

 

 

2

 

 

(k 1)

 

 

(k 1)

 

(k 1)

 

 

 

(k)

... f3

x3

a31x1

 

a32x2

 

 

 

(1 a33)x3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Свойства:

1)Скорость сходимости увеличивается.

2)Можно останавливаться в середине итерации (в середине цикла).

3)Области сходимости той же мощности (некоторые матрицы, которые методом последовательных приближений сходятся, методом Зейделя сходиться не будут, и наоборот).

4)Нет требования к симметричности или положительности .

Метод обеспечения сходимости метода Зейделя.

 

 

 

 

 

 

 

Ax F , если

H

0

 

 

 

 

 

 

 

то две СЛАУ равносильны

HAx H F

тогда Bновое E HA

Выбор H, чтобы все | | < 1 у HA

Итерационный процесс:

1)

 

1

 

 

 

 

 

 

 

 

 

0

0

0

0

 

 

a

 

 

 

 

 

 

 

 

11

 

 

 

 

 

 

 

 

1

 

 

 

 

 

0

0

0

0

 

 

 

 

a

 

 

 

 

 

 

 

 

H

 

22

 

 

 

 

 

 

 

 

1

 

 

 

0

0

 

 

0

0

 

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

32

 

 

 

0

0

0 ...

0

 

 

 

 

 

 

 

1

 

 

0

0

0

0

 

 

 

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

 

nn

2) Если 1) не дало результата (процесс не стал сходиться).

3

 

 

Q

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

Q

 

не нули

A

не нули

2

Q

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

 

nn

 

 

 

 

 

 

 

 

Ищем блоки 2*2, если их нечётное количество, то останется 1 блок

1*1=ann

 

Q

1

0

0

 

0

 

 

 

 

 

 

1

 

 

 

 

 

0

Q 1

0

 

0

 

 

 

H

 

 

2

Q 1

 

 

 

 

 

 

 

0

0

 

0

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

1

 

 

0

0

0

 

 

 

 

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

 

nn

 

3) и т. д.

4

3. Обращение матриц методом окаймления.

А:

На k-ом шаге находится обратная матрица углового минора k k, при этом известна обратная матрица для предыдущего углового минора (k-1)(k-1).

Будем искать Аk-1 в виде (матрица):

 

Pk-1

rk

 

 

qk

1/k

 

Аk*Ak-1 = E = [Ak-1 Uk; Vk k]*[ Pk-1 qk; rk 1/k] =

[Ak-1*Pk-1+Uk*qk

Ak-1*rk+Uk*1/k;

Vk*Pk-1+ k*qkVk*rk+ k*1/k] =

= [Ek-1 0; 0 1]

 

 

 

(1)Ak-1*Pk-1+Uk*qk = E;

(2)Ak-1*rk+Uk*1/k = 0;

(3)Vk*Pk-1+ k*qk = 0T;

(4)Vk*rk+ k*1/k = 1;

Следовательно:

rk = -Аk-1-1 * Uk/k; (5)

Где Аk-1-1 известна на предыдущем шаге. Подставим (5) в (4):

5

Vk*(-Аk-1-1*Uk/k) + k/k = 1; k = k - Vkk-1-1*Uk;

Подставим в (5):

rk = k-1-1 * Uk/ k;

Выразим из (1) Pk-1 и подставим в (3): qk = -Vkk-1/k;

Pk-1 = Аk-1-1 + k-1*Uk*Vk Аk-1-1)/k.

6

4. Преобразование Хаусхолдера.

(Для приведения матрицы n*n к виду Хессенберга ровно за n-2 итерации)

Некоторые определения (воспоминания).

D – диагональная: aij 0 при i j

Q – ортогональная: Q QT QT Q E

R – правая (верхняя) прямоугольная: aij 0

при i j

L – левая (нижняя) треугольная: aij 0 при i j

H – Хессенберга : 1) правая, верхняя aij

0

при

i j 1

2) левая, нижняя aij

0

при

j i 1

Подобные матрицы: если Q, что B = QTAQ (у подобных матриц одинаковые собственные значения)

Конец воспоминаний

Выполняется n-2 шага (начиная с последней строки, и далее вверх). На каждом шаге:

Исключаем нулевые элементы в очередной строке (j<i-1),

Пример i-ого шага: работаем со строкой l = n-i+1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

До главн. диаг.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i =4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x x x x x x

x x x x

 

 

 

x

x

x

0

 

 

0

0

x

x

x

 

 

 

 

 

0

0

x

x

 

 

 

 

1) Рассчитывается величина

 

 

l 1

a2

 

 

 

i

 

j 1

lj

7

 

 

 

T

(a(i), a(i),..., a(i)

, a(i)

 

 

 

 

2)

 

 

 

 

sign(a

);0;0;...0)

U i

 

 

 

 

 

 

 

 

 

l1

l2

 

 

ll 2

ll 1

 

i

ll 1

 

3)

 

H

 

 

 

1

UTU

 

 

(

это скаляр )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i

 

 

2 i

i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

UT

 

 

 

 

 

 

 

 

4)

 

Pi

 

E Ui

 

i

 

 

( это матрица)

 

 

 

 

 

 

H

i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5)

 

A

 

1

P A P

 

- (первую Р не транспонируем, т.к. матрица симметричная)

 

 

i

 

i i

i

 

 

 

 

 

 

 

 

8

5. QR – разложение матрицы.

Задача представить матрицу А в виде произведения: A Q R , где Q – ортогональная ( Q QT E), R -- верхнетреугольная.

Теорема: Если А – верхняя матрица Хессенберга, то у неё существует

QR – разложение, и оно осуществляется последовательным уничтожением поддиагональных нулей.

Q, R QR(A)

Уничтожаем а21 : (в общем случае: аij, где j = i+1)

 

 

 

 

1

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

c

 

s

 

 

 

 

 

 

 

 

 

Берём

Qi

 

 

 

 

 

 

, где

 

 

s

 

c

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

1

 

 

 

 

 

c

 

aii

 

 

,

s

 

 

 

a ji

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a2

a2

 

 

a2

a2

 

 

 

 

ii

ji

 

 

 

 

 

ii

 

 

 

ji

 

 

Получаем:

 

 

A(1) A

 

 

 

 

 

 

 

 

 

 

 

 

 

A

 

Q

 

A

 

 

 

 

 

 

 

 

 

 

(2)

 

 

 

(1)

 

(1)

 

 

 

 

 

R A(n) Q(n 1) A(n 1)

Q(n 1)Q(n 2) A(n 1) ... Q(n 1)Q(n 2) ... Q1A

Домножим слева на

 

 

T T

T

 

Q Q

...Q

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

n

1

 

 

 

QT QT

...QT

 

 

 

1)

R

A

 

Получим:

1

2

 

 

 

 

(n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

QT QT

...QT

 

 

 

1)

Q

 

 

 

 

 

1

2

 

 

 

 

(n

 

 

 

 

 

Алгоритм:

1) Находим Q1

A(2) Q(1) A(1)

Q E Q(T1)

9

2)

A(3) Q(2) A(2) Q Q Q(T2)

n-1)

R Q(n 1) A(n 1)

Q Q QT

(n 1)

10

Соседние файлы в папке шпоры