Решение систем линейных алгебраических уравнений. Метод исключения Жордана и его модификация

Страницы работы

12 страниц (Word-файл)

Содержание работы

Санкт-Петербургский Государственный Университет

Факультет Прикладной Математики – Процессов Управления

Курсовая работа по методам вычислений

Тема 1. Решение систем линейных алгебраических уравнений

Вариант № 20

Выполнил: студентка     

II курса 261 группы          

Мартынова А.М.

Проверил: преп.

Григорьева К.В.

Оценка:         


Санкт-Петербург

2005 г.

Оглавление:

1. Постановка задачи. 3

2. Теоретический вопрос. 4

3. Описание метода. 6

4. Текст программы.. 9

5. Результаты вычислений. 11

6. Список литературы.. 12

1. Постановка задачи

1.  Как влияют на решение систем линейных алгебраических уравнений

                             Ax = C                                            (1)

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

2.  Подробно описать метод исключении Жордана и его модификации (с выбором главного элемента по столбцу, по строке, по всей матрице) для системы (1). Сравнить его по трудоёмкости (т.е. по числу арифметических операций) с методом Гауса.

3.  Составить и отладить программу, реализующую метод Жордана (с выбором главного элемента по строке). Продемонстрировать её работу на примере системы (1) с

;                        



2. Теоретический вопрос

Погрешность решения задачи обуславливается следующими причинами :

- математическое описание задачи является неточным, в частности неточно заданы исходные данные описания (матрицы А и С)

- применяемый для решения метод не является точным: получение точного решения возникающей математической задачи требует неограниченного или неприемлемо большого числа арифметических операций, поэтому вместо точного решения задачи приходится прибегать к приближенному

- при вводе данных на ЭВМ, при выполнении арифметических операций и при выводе данных производятся округления.

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

Пусть решается линейная система Ax = c, A  Мn, c  Сn . Пусть В - алгоритм решения этой системы на идеальной вычислительной системе, так, что x = B(A, c) - точное решение системы и потому x = B(A, c) - отображение на классе невырожденных матриц (x = A-1b). Пусть В - тот же алгоритм, реализованный на реальной вычислительной системе. В результате его проведения получено приближенное решение x’ = В(A, c) . Определим матрицу A’ и вектор c’ из условия x’ = В(A’, c’)   (c’ = A’-1x’), т.е. x’ является точным решением системы A’x’ = c.  Обозначим A’ = A + E, c’ = c + e . Таким образом, точное решение x удовлетворяет системе Ax = c , а приближенное решение x удовлетворяет системе (A + E)x’ = c + e .

Пусть - произвольная матричная норма, согласованная с векторной нормой . Будем считать, что ошибка, вносимая в матрицу при проведении алгоритма, не очень велика: 

 

Отсюда следует, что матрица A + E обратима. Вычислим погрешность x – x’ :

Определение.   Числом обусловленности матрицы A по отношению к матричной норме называется

 , если А невырождена.

 , если А вырождена.

С использованием этого обозначения последнее неравенство можно переписать в виде:

Здесь называется относительной погрешностью в решении х,

называется относительной погрешностью в матрице A ,  называется относительной погрешностью в правой части с.

Часто, чтобы оценить точность полученного приближенного решения х’, вычисляют вектор невязки r = b – Ax’. Оценим относительную погрешность решения через невязку r.

 



3. Описание метода

Пусть требуется решить линейную систему Ax = C:

a11x1 + a12x2 + … + a1nxn = c1,

                                 a21x1 + a22x2 + … + a2nxn = c2,                                   (1)

                                                   …

                                 an1x1 + an2x2 + … + annxn = cn,

Метод Жордана состоит в том, что элементарными преобразованиями над строками матрицы она приводится к единичной, и тогда правая часть будет содержать искомое решение.

Предположим, что a11  отличен  от нуля. Поделив первое уравнение системы на a11, перепишем его в виде:

x1 + a11(1)x2 + … + a11(1)xn = c1(1),

где a1j(1)= a1j/  a11, j=2,…,n,  c1(1) = c1/ a11.  Умножив это уравнеие на ai1 и вычтем из i-го уравнения системы (i = 2,…,n). В результате система примет вид

x1 + a12(1)x2 + … + a11(1)xn = c1(1),

a22(1)x2 + … + a2n(1)xn = c2(1),                                 (1.1)

an2(1)x2 + … + ann(1)xn = cn(1),

где   aij = aij - a1j ai1,    ci(1) = ci(1), - c1(1) ai1,   i, j = 2,…, n.

После k - 1,  k = 1,…,n шагов метода Жордана система преобразована к виду:

x1                           + a1k(k-1)xk + … + a1n(k-1)xn = c1(k-1),

                                   x2                      + a22(k-1)xk + … + a2n(k-1)xn = c2(k-1),

                                         ...                                   …

                                              xk-1 + ak-1,k(k-1)xk + … + ak-1,n(k-1)xn = ck-1(k-1),                 (2)

Похожие материалы

Информация о работе

Тип:
Курсовые работы
Размер файла:
119 Kb
Скачали:
0