Отправляет email-рассылки с помощью сервиса Sendsay

Математика и алгоритмы

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Удивительное рядом" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Июнь 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Макс Викулов

Статистика

220 подписчиков
0 за неделю
←   Все выпуски   →

Математика и алгоритмы


Информационный Канал Subscribe.Ru 
"Математика и алгоритмы". Выпуск 2.

Сегодняшний выпуск посвящен методам решения систем линейных алгебраических уравнений,
или сокращенно СЛАУ. С одной стороны, эта задача кажется настолько тривиальной,
что возникают сомнения в необходимости рассматривать ее, но с другой - великое
множество задач из самых разных разделов науки, которые сводятся к решению СЛАУ.

Существует достаточно много методов решения этих систем, среди которых можно
выделить точные методы и приближенные. Метод решения задачи относится  кклассу
 точных, если в предположении отсутствия округлений он дает точное  решение 
задачи  после  конечного числа  арифметических  и логических операций. К этой
группе относится широко известный метод Гаусса (и его модификация, известная
как метод Жордана-Гаусса).
К классу приближенных относится семейство итерационных методов, имеющих асимптотическую
сходимость к решению системы.


Рассмотрим систему n линейных уравнений с n неизвестными:
     а_{11}х_1 + а_{12}х_2 + ... + а_{1n}х_n = d_1
     а_{21}х_1 + а_{22}х_2 + ... + а_{2n}х_n = d_2
     .............................................         (1)
     а_{n1}х_1 + а_{n2}х_2 + ... + а_{nn}х_n = d_n
где коэффициенты a_{ij} - действительные числа.

Система  уравнений (1) называется совместной, если она имеет решение. Если же
решения  нет,  то  система  называется  несовместной, или противоречивой. Если
система имеет одно решение, то она называется определенной, и неопределенной
-
если она имеет более одного решения.
Для существования единственного решения должно выполнятся условие det[А]<>0.

Метод Гаусса и Холецкого.

Реализация    метода    Гаусса    по   схеме  единственного  деления  требует
выполнения  n(4n^2-3n-4)/6   арифметических   операций.  Рассмотрим решение СЛАУ
методом  Гаусса  по   схеме   Халецкого,  для  реализации  которой  необходимо
n(2n-1) арифметических операции.
Матрица  коэффициентов  А представляется в виде произведения двух треугольных
матриц, т.е.

                                  А=СВ. (2)
 Матрица  С  -  нижняя;  матрица В - верхняя, причем диагональные коэффициенты
матрицы В равны единице.
 Подставим (2) в (1)
                                 СВх = d (3)
 Обозначим
                                    Вх = y

 и перепишем (3) в виде
                                 Сy = d. (4)

 Таким   образом,  первым  шагом  при  решении  поставленной  задачи  является
разбиение матрицы А на две треугольные матрицы С и В.
 Коэффициенты  матриц  С  и В вычисляются последовательно. Сначала вычисляется
первый  столбец  матрицы  С,  затем  вычисляется  первая  строка  матрицы В,
и
элемент  y1=d1/a11;  затем - элементы второго столбца матрицы С, после этого
-
элементы второй строки матрицы В, затем элемент y2 и т.д.
 После  того  как  будут  вычислены  элементы  матриц С и В, а так же вектор
y
находятся искомые неизвестные x_i:

     x_{n-i} = y_{n-i} + \summ_{j=n-i+1}^{x_n = y_n}{b_{n-i,j} x_j}


Рассмотрим подробнее способ разложения матрицы на верхнюю и нижнюю треугольные.

LU-разложение

Триангуляризация или LU-разложение - это, видимо, самый быстрый алгоритм для
произвольных действительных матриц.
Разложение имеет вид: A = LU, где L - нижняя треугольная матрица, U - верхняя
треугольная.
Проблема в том, что диагональный элемент может стать нулевым или очень близким
к нулю. В первом случае вообще не удастся вычислить, во втором случае страдает
точность. Поэтому используют так называемый "выбор ведущего (главного) элемента".
Просто выбираем максимальный по модулю элемент вниз по столбцу, а затем переставляем
строки. Получается разложение
 PA = LU,
где P - перестановочная матрица.
Метод получается достаточно точный, если только матрица не слишком "плохая".
Можно вправо по строке выбирать и переставлять столбцы.

Можно еще модифицировать для удобства:
 PA = LDU,
где D - диагональная матрица, L и U имеют по диагонали единицы.

При этом матрицу можно раскладывать на том же месте, где была матрица A. Внизу
(слева) хранится L, вверху (справа) - U, а по диагонали - D. Единицы не сохраняются.

Из этого разложения имеем:

1) Определитель - произведение диагональных элементов D, домноженное на определитель
матрицы P. Определитель матрицы P либо 1, либо -1 в зависимости от того, какие
были перестановки.

2) Обратную матрицу inv(A) = inv(U)inv(D)inv(L)P.

3) Решение системы уравнений Ax = b.
  inv(P)LDUx = b.
 Сначала решаем Ly = Pb находим y.
 Потом решаем Ux = inv(D)y и находим x.
 Это, по сути, и есть всем известный метод Гаусса.

Если матрица симметричная, то используют разложение
Холецкого:
 A = T'T,
где матрица T нижняя или верхняя треугольная. Опять же, это разложение подправляют
выбором главного элемента. Кроме того, если разложить как A = T'DT, где D - диагональная
матрица, а у T по диагонали единицы, то не нужно извлекать корни.


Метод простой итерации.

 Приведем определения основных норм в пространствах векторов и матриц. Если в
пространстве векторов введена норма ||х||, то согласованно с ней нормой в
пространстве матриц называют норму

                 ||А|| = \sup ||Ax|| / ||х||



  Простейшим итерационным методом решения СЛАУ является метод простой итерации.
Система приводится к виду
                                  х = Вх + е.
 А итерационный процесс записывается в виде
                             x^{k+1} = Bx^k + e, k = 0,1,2,...
 Для сходимости метода при любом начальном приближении необходимо и
достаточно, чтобы все собственные значения матрицы В были по модулю меньше 1.
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное