Паскаль. 
Метод Гаусса

Содержание Введение

1. Теоретический раздел

1.1 Способ Гаусса

1.1.1 Способ единственного деления.

1.1.2 Способ Гаусса с выбором главного элемента по столбцу

1.1.3 Способ Гаусса с выбором главного элемента по всей матрице

1.2 Сравнение итерационных и прямых методов

2. Практическая часть

2.1 Программа решения СЛАУ по методу Гаусса

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

2.1.2 Тестовый пример

2.1.3 Алгоритм программы

2.1.4 Структура разрабатываемой программы

2.1.5 Листинг и результат работы программы

2.1.6 Пример работы программы Список использованной литературы

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

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

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

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

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

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

В случае небольших по объему вычислительных работ хорошим подспорьем могут служить табличный процессор Microsoft Excel, имеющий огромное количество стандартных алгебраических функций, а также встроенный редактор объектно-ориентированного языка Visual Basic for Applications (VBA). Достаточно проста в освоении программа MatCad, так же выполняющая большое количество самых различных функций, в том числе решение СЛАУ и др.

1. Теоретический раздел

1.1 Способ Гаусса

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

1.1.1 Способ единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления

Прямой ход состоит из n — 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 № 0. Будем называть его главным элементом 1-го шага.

Найдем величины

qi1 = ai1/a11 (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, …, qn1.

Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого.

В результате получим эквивалентную систему

a11×1 + a12×2 + a13×3 + … + a1nxn = b1 ,

a22(1)x2 + a23(1)x3 + … + a2n (1)xn = b2(1) ,

a32(1)x2 + a33(1)x3 + … + a3n (1)xn = b3(1) ,

.. .. .. .. .. .. .. .

an2(1)x2 + an3(1)x3 + … + ann (1)xn = bn (1) .

в которой aij (1) и bij (1) вычисляются по формулам

aij (1) = aij? qi1a1j, bi (1) = bi? qi1b1.

2-й шаг. Целью этого шага является ислючение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1)? 0, где a22(1) — коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2. В результате получим систему

a11×1 + a12×2 + a13×3 + … + a1nxn = b1 ,

a22(1)x2 + a23(1)x3 + … + a2n (1) = b2(1) ,

a33(2)x3 + … + a3n (2)xn = b3(2) ,

.. .. .. .. .. .. .. .. .. .

an3(2)x3 + … + ann (2)xn = bn (2) .

Здесь коэффициенты aij (2) и bij (2) вычисляются по формулам

aij (2) = aij (1) — qi2a2j (1), bi (2) = bi (1) — qi2b2(1).

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk (k-1) отличен от нуля, вычислим множители k-го шага

qik = aik (k-1) / akk (k-1) (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk.

После (n — 1)-го шага исключения получим систему уравнений

a11×1 + a12×2 + a13×3 + … + a1nxn = b1 ,

a22(1)x2 + a23(1)x3 + … + a2n (1)xn = b2(1) ,

a33(2)x3 + … + a3n (2)xn = b3(2) ,

.. .. .. .. .. .. .. .. ... .

ann (n-1)xn = bn (n-1) .

матрица A (n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn-1. Осуществляя обратную подстановку, далее последовательно находим xn-1, xn-2, …, x1. Вычисления неизвестных здесь проводятся по формулам

xn = bn (n-1) / ann (n-1),

xk = (bn (k-1) — ak, k+1(k-1)xk+1 — … — akn (k-1)xn) / akk (k-1), (k = n — 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk (k-1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

линейный уравнение гаусс матрица

1.1.2 Способ Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

aij (k) = aij (k-1)? qikakj, bi (k) = bi (k-1)? qikbk (k-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-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk (k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.

1.1.3 Способ Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных

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

На k-м шаге метода среди коэффициентов aij (k-1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk (k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n. На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn-1, …, xj1.

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

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

1.2 Сравнение итерационных и прямых методов

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

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

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

2. Практическая часть

2.1 Программа решения СЛАУ по методу Гаусса

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

Требуется решить систему линейных алгебраических уравнений с вещественными коэффициентами вида

по методу Гаусса.

2.1.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 Структура разрабатываемой программы показана на блок-схемах основной части и вспомогательных модулей

2.1.5 Листинг и результат работы программы

Program Metod_Gauss;

Uses CRT;

Const maxn = 10;

Type

Data = Real;

Vector = Array[1.maxn] of Data;

Matrix = Array[1.maxn, 1. maxn] of Data;

{ Процедура ввода расширенной матрицы }

Procedure ReadSystem (n: Integer; var a: Matrix; var b: Vector);

Var r, i, j: Integer;

Begin

r := WhereY;

GotoXY (2, r);

Write ('A');

For i := 1 to n do begin

GotoXY (i*6+2, r);

Write (i);

GotoXY (1, r+i+1);

Write (i:2);

end;

GotoXY ((n+1)*6+2, r);

Write ('b');

For i := 1 to n do begin

For j := 1 to n do begin

GotoXY (j * 6 + 2, r + i + 1);

Read (a[i, j]);

end;

GotoXY ((n + 1) * 6 + 2, r + i + 1);

Read (b[i]);

end;

End;

{ Процедура вывода результатов }

Procedure WriteX (n :Integer; x: Vector);

Var i: Integer;

Begin

For i := 1 to n do

Writeln ('x', i, ' = ', x[i]);

End;

{ Функция, реализующая метод Гаусса }

Function Gauss (n: Integer; a: Matrix; b: Vector; var x: Vector): Boolean;

Var

k, l, i, j: Integer;

m, q, t: Data;

Begin

For k := 1 to n — 1 do begin

{ Ищем строку l с максимальным элементом в k-ом столбце}

m := 0;

l := 0;

For i := k to n do

If Abs (a[i, k]) > m then begin

l := i;

m := Abs (a[i, k]);

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 := a[k, j];

a[k, j] := a[l, j];

a[l, j] := t;

end;

t := b[k];

b[k] := b[l];

b[l] := t;

end;

{ Преобразуем матрицу }

For i := k + 1 to n do begin

q := a[i, k] / a[k, k];

For j := 1 to n do

If j = k then

a[i, j] := 0

else

a[i, j] := a[i, j] - q * a[k, j];

b[i] := b[i] - q * b[k];

end;

end;

{ Вычисляем решение }

x[n] := b[n] / a[n, n];

For i := n — 1 downto 1 do begin

t := 0;

For j := 1 to n-i do

t := t + a[i, i + j] * x[i + j];

x[i] := (1 / a[i, i]) * (b[i] - t);

end;

Gauss := true;

End;

Var n, i: Integer;

a: Matrix ;

x, b: Vector;

Begin

ClrScr;

Writeln ('Программа решения СЛАУ по методу Гаусса');

Writeln;

Writeln ('Введите порядок матрицы системы (макс. 10)');

Repeat

Write ('>');

Read (n);

Until (n > 0) and (n <= maxn);

Writeln;

Writeln ('Введите расширенную матрицу системы');

ReadSystem (n, a, b);

Writeln;

If Gauss (n, a, b, x) then begin

Writeln ('Результат вычислений по методу Гаусса');

WriteX (n, x);

end

else

Writeln ('Данную систему нельзя решить по методу Гаусса');

Writeln;

End.

2.1.6 Пример работы программы решения СЛАУ по методу Гаусса

Введите порядок матрицы системы (макс. 10) >4

Введите расширенную матрицу системы

A 1 2 3 b

1 3 4 -2 11

2 2 -1 -1 4

3 3 -2 4 11

Результат вычислений по методу Гаусса

x1 = 3

x2 = 1

x3 = 1

Скриншот 1. Результат работы программы при n = 3

Скриншот 2. Результат работы программы при n = 7

Скриншот 3. Аншлаг при Д = 2· 8 — 4· 4 = 0.

1. Малыхина М. П. Программирование на языке высокого уровня Turbo Pascal. — Спб.: БХВ-Петербург, 2006, 544 с.

2. Немнюгин С. А. Turbo Pascal. — Спб.: Питер, 2002. — 496 с.

3. Фаронов В. В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. — М.: Нолидж, 1997. — 616 с.

4. Гусева А. И. Учимся программировать: PASCAL 7.0. Задачи и методы их решения. — М.: Диалог-МИФИ, 1997. — 256 с.

5. Дьяконов В. П. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ: Справочник. — М.: Наука. Гл. ред. физ. -мат. лит., 1987. — 240 с.

6. Сапаров В. Е., Максимов Н. А. Системы стандартов в электросвязи и радиоэлектронике: Учебное пособие для вузов. — М. — Радио и связь, 1985. — 248 с.

7. ГОСТ 19.701−90 (ИСО 5807−85). «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения"/ Cб. ЕСПД. — М.: Изд-во стандартов, 1996. — 157 с.

8. Бахвалов Н., Жидков Н., Кобельков Г. Численные методы. М.: Лаборатория базовых знаний, 2001.632 с.

9. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений / Пер. с англ. М.: Мир, 1980.177с.

10. Самарский А. А., Гулин А. В. Численные методы: Учебное пособие для ВУЗов. М.: Наука, 1989.432с.