Решение систем линейных уравнений.

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

Например:

Коэффициенты сплайнов находятся путем решения СЛАУ. К СЛАУ приводят уравнения частных производных.

Задачи по нахождению собственных значений также приводят к СЛАУ. Таким образом, решение СЛАУ – одна из самых распространенных и важных задач вычислительной математики.

Запишем СЛАУ в общем виде:

 

 

- номер уравнения

- номер неизвестной, на которую умножается коэффициент.

Коэффициенты образуют матрицу

 

Матрица системы столбец неизвестных величин столбец правых частей

Введя эти величины, мы можем записать СЛАУ в виде матричного решения

Важнейшей характеристикой квадратной матрицы является её определитель( )

Число возможных значений

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

,

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

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

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

Методы решения СЛАУ делятся на 2 группы:

1)прямые

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

Итерационные

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

Например:

Уравнений с преобладанием диагональных элементов, либо системы со слабо заполненными матрицами.

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

Наиболее распространенным среди прямых методов является метод Гаусса.

Метод 14

Метод Гаусса.

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

Прямой ход состоит в следующем:

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

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

Рассмотрим процесс исключения подробнее:

На -ом шаге исключается

Запишем -ое уравнение:

Исключим с помощью этого уравнения из уравнения с номером

Для исключения из -го уравнения вычитаем -ое, умноженное на .

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

При этом изменяется свободный член

 

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

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, начиная с . Сначала находится . Далее, используя это значение, находится и так далее.

Например:

На - ом шаге обратного хода неизвестные находятся с помощью выражения.

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

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

В методе Гаусса объём вычислений пропорционален . Существует практически значимые случаи, когда объём вычислений при решении СЛАУ можно резко сократить.

 

Метод 15

Метод прогонки.

Метод прогонки является модификацией метода Гаусса для частного случая с трёхдиагональной матрицей. Такие системы возникают при численном решении уравнений математической физики.

Другой пример: коэффициенты сплайна третьей степени находятся путём решения систем с трёхдиагональной матрицей.

В методе прогонки объём вычислений растет пропорционально . Запишем систему уравнений, которая решается методом прогонки.

 

 

Общий вид уравнений с трёхдиагональной матрицей

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

Рассмотрим первый этап (прямой ход метода прогонки)

Для этого неизвестный выражаем через , таким образом:

,

где , - неизвестные пока (прогоночные) коэффициенты. На первом как раз и находится эти коэффициенты. Сравним это уравнение при с первым уравнением системы

И из сравнения находим, что

Заменим i-ое уравнение системы, выразив в нём с помощью

Сравнивая с

Получаем рекуррентные соотношения для нахождения прогоночных коэффициентов.

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

Отсюда

Это фактически начало обратного хода метода прогонки.

После этого последовательно находим …….и т.д. вплоть до .

Метод 16

Уточнение решения (итерационный метод).

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

Рассмотрим итерационный процесс позволяющий уточнить решения на следующем итерационном шаге. Пусть решается система

……………………………

Пусть на k-ом итерационном шаге получено решение в виде , , …, , где k-это номер итерационного шага.

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

В результате получим систему

 

……………………………

Вычтем из каждого уравнения 1-ой системы уравнение 2-ой системы и получим систему вида

……………………………

Отсюда

Это невязка для уравнений с соответствующим номером.

Теперь мы получаем систему решением, которой будут соотношения уточняющие решение.

………………..

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

Метод 17

Метод Гаусса-Зейделя.

Является одним из самых распространённых итерационных методов. Это связано с простотой метода. Перепишем уравнение системы, выразив из первого уравнения, - из второго и т.д.

Получится система, которая имеет вид:

……………………………………….

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

Сначала задаётся начальное приближение и на 1-ом итерационном шаге с помощью 1-го уравнения находится

и т.д. до .

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

, для любого i

И, по крайней мере, хотя бы в одном уравнении модуль должен быть большим.

Тема №5

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться:

Популярное:

1. I) Получение передаточных функций разомкнутой и замкнутой системы, по возмущению относительно выходной величины, по задающему воздействию относительно рассогласования .
2. I. Естествознание в системе науки и культуры
3. I. Логистика как системный инструмент.
4. I. ПОЧЕМУ СИСТЕМА МАКАРЕНКО НЕ РЕАЛИЗУЕТСЯ
5. I. РАЗВИТИИ ЛЕКСИЧЕСКОЙ СИСТЕМЫ ЯЗЫКА У ДЕТЕЙ С ОБЩИМ НЕДОРАЗВИТИЕМ РЕЧИ
6. II. О ФИЛОСОФСКОМ АНАЛИЗЕ СИСТЕМЫ МАКАРЕНКО
7. II. Система обязательств позднейшего права
8. II. Соотношение — вначале самопроизвольное, затем систематическое — между положительным мышлением и всеобщим здравым смыслом
9. III ГЛАВА. ИНТЕРЬЕР И АРХИТЕКТУРНО – ПРОЕКТИРОВОЧНОЕ РЕШЕНИЕ ШКОЛЫ БУДУЩЕГО
10. V) Построение переходного процесса исходной замкнутой системы и определение ее прямых показателей качества
11. VI. ОБСЛЕДОВАНИЕ БОЛЬНОГО ПО ОРГАНАМ И СИСТЕМАМ
12. VIII. Общение и система взаимоотношений