Автоматизация решения систем линейных алгебраических уравнений (стр. 2 из 4)
2.2 Метод Гаусса. Исключение неизвестных
Метод Гаусса является универсальным, так как применим для исследования на совместность и решение не только квадратных, но и любых СЛАУ. Суть метода: СЛАУ кратко записывают в виде расширенной матрицы, которую с помощью элементарных преобразований над строками приводят к ступенчатому виду.
Этот процесс называют прямым ходом метода Гаусса. В каждой строке ступенчатой матрицы соответствует свое алгебраическое уравнение.
Ступенчатая СЛАУ совместна только тогда, когда она не содержит строк вида <0 0...0 | c>, где с≠0, так как им соответствуют противоречивые равенства вида 0=с. Строки вида <0 0...0 | 0> отбрасываются, так как им соответствует тождество 0≡0.
Решение совместной СЛАУ ступенчатого вида находят так: из последнего уравнения СЛАУ находится значение неизвестной xn и подставляется в вышестоящее уравнение, чтобы найти значение xn-1. Далее, используя значения этих двух неизвестных, поднимаются на ступеньку выше и находят значение xn-2 и так далее. Последним находят значение неизвестной x1 из 1-ого уравнения. Описанный процесс называется обратным ходом метода Гаусса.
2.3 Однородная СЛАУ
Однородная СЛАУ имеет вид
a11x1+a12x2+... +a1nxn=0a21x1+a22x2+... +a2nxn=0
………... ... ... ... ... ………, (2.2)
am1x1+am2x2+... +amnxn=0
В однородной СДАУ нулевой столбец не меняется при элементарных преобразованиях над строками расширенной матрицы. Поэтому в ней ранг матрицы коэффициентов всегда равен рангу расширенной матрицы. (r (A) =r (Ab)).
Тогда, по теореме Кронекера - Капелли любая однородная СЛАУ всегда совместна и, согласно ее виду, всегда имеет нулевое (тривиальное) решение: x1=... =xn=0. Если при этом ранг матрицы коэффициентов равен числу неизвестных (r (A) =n), то для однородной СЛАУ нулевое решение является единственно возможным.
Теорема 1.
Для того чтобы однородная СЛАУ имела нулевые решения, необходимо и достаточно, чтобы ранг матрицы коэффициентов был меньше числа неизвестных (r (A) <n).
Доказательство.
1) Необходимость. Предположим обратное, то есть, что r (A) =n, где n - число неизвестных. Тогда порядок базисного минора Mn будет равен n, так как r (Mn) =r (A) =n. Следовательно, по формулам Крамера однородная СЛАУ будет иметь единственное решение - нулевое: xi = Δi/ Δ = 0, где Δi = 0,a Δ ≠ 0. Таким образом, при r (A) =n однородная СЛАУ ненулевых решений не имеет.
2) Достаточность. Пусть r (A) <n, тогда по следствию 2 теоремы Кронекера-Копелли однородная СЛАУ будет совместной и неопределенной, то есть она будет иметь бесконечное множество решений, в том числе и нулевых. Fin.
Теорема 2.
Для того чтобы квадратная однородная СЛАУ имела нулевые решения, необходимо и достаточно, чтобы ее главный определитель был равен нулю (Δ=0). Доказательство.
1) Необходимость. По вышеприведенной теореме 1, если однородная СЛАУ имеет нулевые решения, то ранг ее матрицы коэффициентов должен быть меньше числа неизвестных (r (A) <n). Следовательно, главный определитель квадратной однородной СЛАУ должен быть равен нулю (Δ=0).
2) Достаточность. Если главный определитель квадратной однородной СЛАУ равен нулю (Δ=0), то ранг ее матрицы коэффициентов будет меньше числа неизвестных (r (A) <n). Поэтому такая СЛАУ имеет бесконечное множество ненулевых решений. Fin.
Теорема 2.
Для того чтобы квадратная однородная СЛАУ имела нулевые решения, необходимо и достаточно, чтобы ее главный определитель был равен нулю (Δ=0). Доказательство.
1) Необходимость. По вышеприведенной теореме 1, если однородная СЛАУ имеет нулевые решения, то ранг ее матрицы коэффициентов должен быть меньше числа неизвестных (r (A) <n). Следовательно, главный определитель квадратной однородной СЛАУ должен быть равен нулю (Δ=0).
2) Достаточность. Если главный определитель квадратной однородной СЛАУ равен нулю (Δ=0), то ранг ее матрицы коэффициентов будет меньше числа неизвестных (r (A) <n). Поэтому такая СЛАУ имеет бесконечное множество ненулевых решений.
3. Алгоритм решения задачи
3.1 Водные данные
Входными данными в алгоритме решения систем линейных уравнений методом Гаусса являются:
А: массив [1…N, 1…N] вещ. {матрица}
В: массив [1…N] вещ. {массив свободных коэффициентов}
N: цел. {размер матрицы}
3.2 Промежуточные данные
Промежуточные данные в алгоритме решения систем линейных уравнений методом Гаусса являются:
l: цел. {Индекс элементов. Номер строки,
которую обрабатываем}
i: цел {номер "Базовой строки"}
К: вещ. {множитель для l - ой строки}
kol: цел {количество нулей в текущей строке}
S: вещ. {сумма элементов, вычисляемая
при обратном ходе метода Гаусса}
3.3 Входные данные
Выходные данные в алгоритме решения систем линейных уравнений методом Гаусса являются:
х: массив [1…N] вещ. {массив ответов}
Rez: цел. {количество решений матрицы:
0 - ни одного; 1 - одно; 2 - ∞}
3.4 Алгоритм
На рисунке 3.1 изображен ввод размера матрицы, который должен быть больше нуля
Рисунок 3.1 Ввод
На рисунке 3.2 изображен цикл ввода коэффициентов.
 |
для i: =1 до N
Рисунок 3.2 Цикл.
На рисунке 3.3 изображен цикл приведения матрицы к ступенчатому виду и нахождение корней.
 |
для i: =1 до N-1
Рисунок 3.3 Ступенчатый вид
На рисунке 3.4 показано что происходит если переменной Rez присваиваются значения 0, 1,2.
Rez: =1
для i: =1 до N
Рисунок 3.4 Переменная Rez
Рисунок 3.5 является продолжением рисунка 3.4
если Rez=1 to
для i:=N-1 до 1 шаг -1{Вывод матрицы А и вектора х}
Иначе
Если Rez = 0 то
Вывод
Иначе вывод
Рисунок 3.5 Переменная Rez.4. Проектирование интерфейса
В данном программном продукте был использован текстовый интерфейс, т.к. разработчик отдает ему большее предпочтение. Был выбран комбинированный режим. Текстовый - для написания интерфейса, графический - для рисования графиков.
Меню интерфейса состоит из 5 пунктов каждому из которых соответствует своя цифра:
пункт вида "1 - Теория", означает, что для вызова теоретической информации нужно нажать клавишу 1;
пункт вида "2 - Пример", означает, что для вызова примера решения СЛАУ методом Гаусса нужно нажать клавишу 2;
пункт вида "3 - Решение", означает, что для вызова диалогового окна, где будет предложено пользователю ввести свои коэффициенты для решении СЛАУ, нужно нажать клавишу 3;
пункт вида "4 - Справка", означает, что для вызова справочной информации нужно нажать клавишу 4;
пункт вида "5 - Выход", означает, что для выхода из программы нужно нажать клавишу 1;
Статусная строка отображает информацию следующего вида:
подсказки пользователю, относительно дальнейших действий: " Нажмите номер пункта меню", "Для перехода укажите номер страницы (от 1 до 6), "Для возврата в меню нажмите Esc, для вывода справки нажмите 0", "Для возврата назад нажмите 1".
5. Описание программной реализации
5.1 Функционально-логическая схема программы
Данная схема отражает укрупненный алгоритм работы программы с учетом интерфейсных решений (см. рисунок 5.1).
Вначале происходит прорисовка главного окна программы, в результате чего на экран выводятся 5 пунктов главного меню. Если выбрана первый пункт (1 - Теория), то происходит вывод теоретической информации на экран. Если выбрана второй пункт меню (2 - Пример) - вывод примера решения СЛАУ на экран. Если выбрана третий пункт (3 - Решение) - происходит решение СЛАУ методом Гаусса. Если выбран четвертый пункт (4 - Справка) - на экран выводится справочная информация по методу Гаусса. Если выбран пятый пункт (5 - Выход) - происходит полный выход из программы. Если не выбран ни один пункт меню, на экране ничего не происходит.
 |
Рис.5.1 Функционально - логическая схема программы
5.2 Описание процедур и функций
Процедура LoadFile (Name: string); - открывает текстовые файлы.
Name- имя открываемого файла.
Процедура menu; - выводит на экран главное меню.
Процедура menuTeorii; - выводит на экран файл с меню для теории.
Процедура menuSpravki; - выводит на экран файл с меню для справки.
Процедура menuPrimera; - выводит на экран файл с меню для примера.
Процедура Spravka (varn: char); - выводит на экран справочную информацию.
n- номер открываемой страницы.
Процедура Teoria ( varn: char); - выводит на экран теоретическую информацию.
n- номер открываемой страницы.
Процедура Grafik (а1, b1, c1, a2, b2, c2, xc, yc: real); - выводит на экран график.
а1, b1, c1, a2, b2, c2, xc, yc- коэффициенты матрицы.
Процедура Vvod (varx: real; varcode: integer); - процедура для ввода вещественного числа.
x- вещественное число,
соde- переменная ошибки.
Процедура Vvod1 (varn: integer); - процедура для ввода целого числа.
n- целое число;
Процедура Rewenie; - решение СЛАУ.