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

Метод Гаусса

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

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

Метод Гаусса относится к точным методам решения систем линейных уравнений вида , где Х – вектор-столбец неизвестных ,  - матрица коэффициентов, В – вектор-столбец свободных членов . Как известно из курса линейной алгебры, метод Гаусса заключается в приведении матрицы системы к треугольному виду (прямой ход метода) и затем в последовательном нахождении неизвестных  (обратный ход)_.

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

.

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

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

Нахождение неизвестных при обратном ходе метода осуществляется по формуле:

.

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

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

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

,

где - сумма индексов переставлявшихся строк.

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

Основным недостатком метода Гаусса является большое число выполняемых в процессе решения арифметических операций - .

 

3.2. Метод простых итераций

Точные методы решения линейных систем применяются для систем относительно небольшой размерности (до 10³). Для решения систем больших размерностей применяются итерационные методы, в частности, метод простых итераций.

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

Теорема 3.1. Пусть имеется система линейных уравнений вида  (где С - невырожденная квадратная матрица). Предположим, - произвольный вектор (начальное приближение). Построим последовательность векторов

 - последовательные приближения (итерации).

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

 

Метод Зейделя

Пусть дана система уравнений . Предположим, что все диагональные элементы матрицы А отличны от нуля: ( ,  ).

Поделим каждое  i -тое уравнение на a_ii:

В правой части каждого из уравнений оставим только i–е неизвестные:

,

       Тогда система запишется в виде x = Cx + d, где

 ,  

Выберем начальное приближение . Каждое следующее приближение вычисляется по следующим формулам:

,

где  - i-я компонента k-го приближения.

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

 

Для сходимости метода Зейделя достаточно выполнение условия:

 

 

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

Метод бисекций

Пусть задана непрерывная функция , и требуется найти корни уравнения .

Первым этапом решения является локализация корней, которая заключается в определении отрезка [а, b], на котором функция принимает значения разных знаков, т.е. . Тогда по теореме Больцано-Коши внутри отрезка существует такая точка c, что . Определение числа корней функции и выделение содержащих их отрезков осуществляется с помощью исследования графика функции.

Пусть отрезок [a, b] определен. Итерационный метод бисекций состоит в построении вложенных последовательности отрезков , на концах которых функция принимает значения разных знаков. Каждый последующий отрезок получают делением пополам предыдущего. Процесс построения последовательности отрезков позволяет найти корень функции  с любой заданной точностью.

Опишем один шаг итераций. Пусть на (п-1)-м шаге найден отрезок  такой, что . Разделим его пополам точкой  и вычислим значение . Если , то c – корень уравнения. Если , то из двух половин отрезка выберем ту, на концах которой функция принимает разные знаки, т.к. корень находится в этой половине:

, если ,

, если .

Если точность нахождения корня e задана, то итерационный процесс продолжается до тех пор, пока длина отрезка станет не меньше 2e. Тогда координата середины отрезка и есть значение корня с требуемой точностью.

Метод бисекций – надежный способ отыскания простых корней функции. Он сходится для любых непрерывных, в том числе и недифференцируемых функций, однако скорость сходимости невелика. Для достижения заданной точности e необходимо совершить N итераций, где

.

       Метод неприменим для отыскания кратных корней четного порядка. В случае отыскания корней нечетной кратности он менее точен.

Метод итераций

Рассмотрим уравнение вида .

Функция  удовлетворяет условию Липшица на отрезке [a; b] с константой , если справедливо следующее неравенство:

     

Теорема 4.1. Пусть функция  определена на некотором отрезке
[x₀; x₀+ r] и удовлетворяет на нем условию Липшица с константой  (0< a< 1). Пусть также справедливо условие .

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

,

где x ₀ - начальное приближение, .

 

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

Поделиться: