Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

Содержание Введение 1. Теоретическая часть 1. Метод Гаусса 2. Метод Зейделя 3. Сравнение прямых и итерационных методов 2. Практическая часть 2.1 Программа решения системы линейных уравнений по методу Гаусса 2.2 Программа решения системы линейных уравнений по методу Зейделя 10 Введение Решение систем линейных алгебраических уравнений одна из основных задач вычислительной

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

Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя обьем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач все большей размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты

машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ. К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего чила элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются

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

Гбайт. 1. Теоретическая часть 1. Метод Гаусса Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод который также называют методом последовательного исключения неизвестных известен в различных вариантах уже более 2000 лет. Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с верхней треугольной матрицей.

Вычисления значений неизвестных производят на этапе обратного хода. 1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления. Прямой ход состоит из n 1 шагов исключения. 1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i 2, 3 n. Предположим, что коэффициент a0. Будем называть его главным элементом 1-го шага.

Найдем величины qi1 ai1a11 i 2, 3 n, называемые множителями 1-го шага. Вычтем последовательно из второго, третьего n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31 qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему a11x1 a12x2 a13x3 a1nxn b1 , a221x2 a231x3 a2n1xn b21 , a321x2 a331x3 a3n1xn b31 an21x2 an31x3 ann1xn bn1 . в которой aij1 и bij1 вычисляются по формулам aij1

aij - qi1a1j , bi1 bi - qi1b1. 2-й шаг. Целью этого шага является ислючение неизвестного x2 из уравнений с номерами i 3, 4 n. Пусть a221 0, где a221 коэффициент, называемый главным или ведущим элементом 2-го шага. Вычислим множители 2-го шага qi2 ai21 a221 i 3, 4 n и вычтем последовательно из третьего, четвертого n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42 qm2. В результате получим систему a11x1 a12x2 a13x3 a1nxn b1 , a221x2 a231x3 a2n1 b21 , a332x3 a3n2xn b32

an32x3 ann2xn bn2 . Здесь коэффициенты aij2 и bij2 вычисляются по формулам aij2 aij1 qi2a2j1 , bi2 bi1 qi2b21. Аналогично проводятся остальные шаги. Опишем очередной k-й шаг. k-й шаг. В предположении, что главный ведущий элемент k-го шага akkk 1 отличен от нуля, вычислим множители k-го шага qik aikk 1 akkk 1 i k 1 n и вычтем последовательно из k 1-го n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk1,k, qk2,k qnk.

После n - 1-го шага исключения получим систему уравнений a11x1 a12x2 a13x3 a1nxn b1 , a221x2 a231x3 a2n1xn b21 , a332x3 a3n2xn b32 annn 1xn bnn 1 . матрица An-1 которой является верхней треугольной. На этом вычисления прямого хода заканчиваются. Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn 1.

Осуществляя обратную подстановку, далее последовательно находим xn 1, xn 2 x1. Вычисления неизвестных здесь проводятся по формулам xn bnn 1 annn 1, xk bnk 1 ak,k1k 1xk1 aknk 1xn akkk 1, k n 1. Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akkk 1. Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может

быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности. 1.1.2. Метод Гаусса с выбором главного элемента по столбцу схема частичного выбора. Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i k 1 n преобразуются по формулам aijk aijk 1 - qikakj , bik bik 1 - qikbkk 1 , i k 1 n.

Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей qik. В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что qik 1 для всех k 1, 2 n 1 и i k 1 n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной

xk в уравнениях с номерами i k 1 n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akkk-1. После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления. 1.1.3. Метод Гаусса с выбором главного элемента по всей матрице схема полного выбора. В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге мтода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого. На k-м шаге метода среди коэффициентов aijk 1 при неизвестных в уравнениях системы с номерами i k n выбирают максимальный по модулю коэффициент aikjkk-1.

Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i k 1 n. На этапе обратного хода неизвестные вычисляют в следующем порядке xjn, xjn 1 xj1. 1.2. Метод Зейделя 1.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений Ax b с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x Bx c. Здесь B квадратная матрица с элементами bij i, j 1, 2 n, c вектор-столбец с элементами cij i 1, 2 n. В развернутой форме записи система имеет следующий вид x1 b11x1 b12x2 b13x3 b1nxn c1 x2 b21x1 b22x2 b23x3 b2nxn c2 xn bn1x1 bn2x2 bn3x3 bnnxn cn Вообще говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы. Самый простой способ приведения системы к виду, удобному для итераций, состоит в

следующем. Из первого уравнения системы выразим неизвестное x1 x1 a11 1 b1 a12x2 a13x3 a1nxn, из второго уравнения неизвестное x2 x2 a21 1 b2 a22x2 a23x3 a2nxn, и т. д. В результате получим систему x1 b12x2 b13x3 b1,n 1xn 1 b1nxn c1 , x2 b21x1 b23x3 b2,n 1xn 1 b2nxn c2 , x3 b31x1 b32x2 b3,n 1xn 1 b3nxn c3 xn bn1x1 bn2x2 bn3x3 bn,n 1xn 1 cn , в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам bij aij aii, ci bi aii

i, j 1, 2 n, j i Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы A были ненулевыми. 1.2.1. Описание метода. Введем нижнюю и верхнюю треугольные матрицы 0 0 0 0 0 b12 b13 b1n b21 0 0 0 0 0 b23 b2n B1 b31 b32 0 0 , B2 0 0 0 b3n bn1 bn2 bn3 0 0 0 0 0 Заметим, что B B1 B2 и поэтому решение x исходной системы удовлетворяет равенству x

B1x B2 x c . Выберем начальное приближение x0 x10, x20 xn0T. Подставляя его в правую часть равенства при верхней треугольной матрице B2 и вычисляя полученное выражение, находим первое приближение x1 B1x0 B2x1 Подставляя приближение x1, получим x2 B1x1 B2x2 Продолжая этот процесс далее, получим последовательность x0, x1 xn, приближений к вычисляемых по

формуле xk1 B1k1 B2k c или в развернутой форме записи x1k1 b12x2k b13x2k b1nxnk c1 , x2k1 b21x1k1 b23x3k b2nxnk c2 , x3k1 b31x1k1 b32x2k1 b3nxnk c3 xnk1 bn1x1k1 bn2x2k1 bn3x3k1 cn . Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим xik1 xik aii 1j1i 1 aijxjk1 j1n aijxik bi. Тогда достаточным условием сходимоти метода Зейделя будет j1, ji n aij aii условие доминированния диагонали.

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений. 1.3. Сравнение прямых и итерационных методов Системы линейных алгебраических уравнений можно решать как с помощью прямых, так и и итерационных методов. Для систем уравнений средней размерности чаще использют прямые методы.

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

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

решения большой системы уравнений требует серьезного использования ее структуры, специальных знаний и определенного опыта. 2. Практическая часть 2.1 Программа решения систем линейных уравнений по методу Гаусса 2.1.1. Постановка задачи. Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида a11x1 a12x2 a1nxn b1 , a21x2 a22x2 a2nxn b2 an1x1 an2x2 annxn bn для n 10 по методу Гаусса. 2.1.2. Тестовый пример. 3,2x1 5,4x2 4,2x3 2,2x4 2,6 ,

2,1x1 3,2x2 3,1x3 1,1x4 4,8 , 1,2x1 0,4x2 0,8x3 0,8x4 3,6 , 4,7x1 10,4x2 9,7x3 9,7x4 8,4 , x1 5, x2 4, x3 3, x4 2. 2.1.3. Описание алгоритма. В данной программе реализован метод Гаусса со схемой частичного выбора. В переменную n вводится порядок матрицы системы. С помощью вспомогательной процедуры ReadSystem в двумерный массив a и одномерный массив b вводится

c клавиатуры расширенная матрица системы, после чего оба массива и переменная n передаются функции Gauss. В фукции Gauss для каждого k-го шага вычислений выполняется поиск максимального элемента в k-м столбце матрицы начинаяя с k-й строки. Номер строки, содержащей максимальный элемент сохраняеется в переменной l. В том случае если максимальный элемент находится не в k-й строке, строки с номерами k и l меняются местами. Если же все эти элементы равны нулю, то происходит прекращение выполнения функции

Gauss c результатом false. После выбора строки выполняется преобразование матрицы по методу Гаусса. Далее вычисляется решение системы и помещается в массив x. Полученное решение выводится на экран при помощи вспомогательной процедуры WriteX. 2.1.4. Листинг программы и результаты работы Uses CRT Const maxn 10 Type Data Real Matrix Array1 maxn,

1 maxn of Data Vector Array1 maxn of Data Процедура ввода расширенной матрицы системы Procedure ReadSystemn Integer var a Matrix var b Vector Var i, j, r Integer Begin r WhereY GotoXY2, r WriteA For i 1 to n do begin GotoXYi62, r Writei GotoXY1, ri1 Writei2 end GotoXYn162, r Writeb For i 1 to n do begin

For j 1 to n do begin GotoXYj 6 2, r i 1 Readai, j end GotoXYn 1 6 2, r i 1 Readbi end End Процедура вывода результатов Procedure WriteXn Integer x Vector Var i Integer Begin For i 1 to n do Writelnx, i xi End Функция, реализующая метод Гаусса Function Gaussn Integer a Matrix b Vector var xVector

Boolean Var i, j, k, l Integer q, m, t Data Begin For k 1 to n - 1 do begin Ищем строку l с максимальным элементом в k-ом столбце l 0 m 0 For i k to n do If Absai, k m then begin m Absai, k l i end Если у всех строк от k до n элемент в k-м столбце нулевой, то система не имеет однозначного решения If l 0 then begin Gauss false Exit end Меняем местом l-ую строку с k-ой

If l k then begin For j 1 to n do begin t ak, j ak, j al, j al, j t end t bk bk bl bl t end Преобразуем матрицу For i k 1 to n do begin q ai, k ak, k For j 1 to n do If j k then ai, j 0 else ai, j ai, j - q ak, j bi bi - q bk end end Вычисляем решение xn bn an, n For i n - 1 downto 1 do begin t 0 For j 1 to n-i do t t ai, i j xi j xi 1 ai, i bi - t end

Gauss true End Var n, i Integer a Matrix b, x Vector Begin ClrScr WritelnПрограмма решения систем линейных уравнений по методу Гаусса Writeln WritelnВведите порядок матрицы системы макс. 10 Repeat Write Readn Until n 0 and n maxn Writeln WritelnВведите расширенную матрицу системы ReadSystemn, a, b

Writeln If Gaussn, a, b, x then begin WritelnРезультат вычислений по методу Гаусса WriteXn, x end else WritelnДанную систему невозможно решить по методу Гаусса Writeln End. Программа решения систем линейных уравнений по методу Гаусса Введите порядок матрицы системы макс. 10 4 Введите расширенную матрицу системы A 1 2 3 4 b 1 3.2 5.4 4.2 2.2 2.6 2 2.1 3.2 3.1 1.1 4.8 3 1.2 0.4 -0.8 -0.8 3.6 4 4.7 10.4 9.7 9.7 -8.4

Результат вычислений по методу Гаусса x1 5.0E00 x2 -4.0E00 x3 3.0E00 x4 -2.0E00 2.2 Программа решения систем линейных уравнений по методу Зейделя 2.2.1. Постановка задачи. Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида a11x1 a12x2 a1nxn b1 , a21x2 a22x2 a2nxn b2 an1x1 an2x2 annxn bn для n 10 по методу Зейделя. 2.2.2. Тестовый пример. 4,1x1 0,1x2 0,2x3 0,2x4 21,14 ,

0,3x1 5,3x2 0,9x3 0,1x4 17,82 , 0,2x1 0,3x2 3,2x3 0,2x4 9,02 , 0,1x1 0,1x2 0,2x3 9,1x4 17,08 , x1 5,2, x2 4,2, x3 3, x4 1,8. 2.2.3. Описание алгоритма. В переменную n вводится порядок матрицы системы, в переменную e максимальная абсолютная погрешность. С помощью вспомогательной процедуры ReadSystem в двумерный массив a и одномерный массив b вводится c клавиатуры расширенная матрица системы.

Начальное прибижение предполагается равным нулю. Оба массива и переменные n и e передаются функции Seidel. В функции Seidel исследуется сходимость системы, и в том случае если система не сходится, выполнение функции прекращается с результатом false. В ходе каждой итерации вычисляется новое приближение и и абсолютная погрешность. Когда полученная погрешность становится меньше заданной, выполнение функции прекращается. Полученное решение выводится на экран при помощи вспомогательной процедуры

WriteX. 2.2.4. Листинг программы и результаты работы. Uses CRT Const maxn 10 Type Data Real Matrix Array1 maxn, 1 maxn of Data Vector Array1 maxn of Data Процедура ввода расширенной матрицы системы Procedure ReadSystemn Integer var a Matrix var b Vector Var i, j, r Integer Begin r WhereY GotoXY2, r WriteA

For i 1 to n do begin GotoXYi 6 2, r Writei GotoXY1, r i 1 Writei2 end GotoXYn 1 6 2, r Writeb For i 1 to n do begin For j 1 to n do begin GotoXYj 6 2, r i 1 Readai, j end GotoXYn 1 6 2, r i 1 Readbi end End Процедура вывода результатов Procedure WriteXn Integer x Vector Var i Integer Begin

For i 1 to n do Writelnx, i xi End Функция, реализующая метод Зейделя Function Seideln Integer a Matrix b Vector var x Vector e Data Boolean Var i, j Integer s1, s2, s, v, m Data Begin Исследуем сходимость For i 1 to n do begin s 0 For j 1 to n do If j i then s s Absai, j If s Absai, i then begin

Seidel false Exit end end Repeat m 0 For i 1 to n do begin Вычисляем суммы s1 0 s2 0 For j 1 to i - 1 do s1 s1 ai, j xj For j i to n do s2 s2 ai, j xj Вычисляем новое приближение и погрешность v xi xi xi - 1 ai, i s1 s2 - bi If Absv - xi m then m Absv - xi end Until m e Seidel true End Var n, i Integer a Matrix b, x

Vector e Data Begin ClrScr WritelnПрограмма решения систем линейных уравнений по методу Зейделя Writeln WritelnВведите порядок матрицы системы макс. 10 Repeat Write Readn Until n 0 and n maxn Writeln WritelnВведите точность вычислений Repeat Write Reade Until e 0 and e 1 Writeln WritelnВведите расширенную матрицу системы

ReadSystemn, a, b Writeln Предполагаем начальное приближение равным нулю For i 1 to n do xi 0 If Seideln, a, b, x, e then begin WritelnРезультат вычислений по методу Зейделя WriteXn, x end else WritelnМетод Зейделя не сходится для данной системы Writeln End. Программа решения систем линейных уравнений по методу

Зейделя Введите порядок матрицы системы макс. 10 4 Введите точность вычислений .01 Введите расширенную матрицу системы A 1 2 3 4 b 1 4.1 0.1 0.2 0.2 21.14 2 0.3 5.3 0.9 -0.1 -17.82 3 0.2 0.3 3.2 0.2 9.02 4 0.1 0.1 0.2 -9.1 17.08 Результат вычислений по методу Зейделя x1 5.208E00 x2 -4.2028E00 x3 3.03E00 x4 -1.80E00