Пример 1.9.4-1. Решить систему методом Зейделя, выполнив две итерации

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

 

Методы решения систем линейных уравнений (СЛУ) обычно разделяют на две большие группы:

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

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

 

В общем виде СЛУ записывается следующим образом:

(1.9.1-1)

 

Другая форма записи – матричная форма:

(1.9.1-2)

 

где А – матрица коэффициентов, Х – вектор неизвестных, В – вектор свободных членов.

Решением системы (1.9.1-1) является такой набор значений неизвестных , при котором n уравнений системы обращаются в тождества.

СЛУ может иметь единственное решение, не иметь решения, иметь бесконечное множество решений. Поэтому перед тем как решать СЛУ, надо исследовать ее на предмет существования единственного решения. Исследование сводится к следующему:

· если то система имеет единственное решение;

 

· если det A= , то система не имеет решения или имеет бесконечное множество решений.

 

Для случая СЛУ с двумя неизвестными, это можно продемонстрировать графически (рис. 1.9.1-1).

 

Рис. 1.9.1-1

 

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

Рис. 1.9.1-2

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

 

Метод Гаусса

 

Идея метода Гаусса заключается в последовательном исключении неизвестных из уравнений системы. Рассмотрим этот метод на примере СЛУ с тремя неизвестными. Такая система имеет следующий общий вид:

 

(1.9.2-1)

 

Процесс решения СЛУ методом Гаусса сводится к последовательному исключению из (2) и (3) уравнения, а затем из (3) уравнения. Таким образом, из СЛУ (1.9.2-1) получают эквивалентную систему, имеющую треугольную матрицу (прямой ход), а затем получают решение (обратный ход).

 

Прямой ход решения системы (1.9.2-1) заключается в следующем.

1) Домножим уравнение (1) на и вычтем из (2) уравнение (1):

.

 

Уравнение (2) теперь имеет вид:

2) Домножим уравнение (1) на и вычтем из (3) уравнение (1):

.

 

Уравнение (3) теперь имеет вид: , исключен из уравнения (2) и (3).

3) Домножим уравнение (2) на и вычтем из (3) уравнение (2):

.

 

Уравнение (3) теперь имеет вид:

В результате преобразований СЛУ (1.9.2-1) имеет вид:

 

. (1.9.2-2)

 

Последовательно решая уравнения (3), (2) и (1) (обратный ход), найдем решение системы.

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

 

Пример 1.9.2-1. Решить систему уравнений методом Гаусса .

 

 

 

Решение имеет вид:

 

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

 

Пусть задана СЛУ с nнеизвестными:

(1.9.3-1)

 

Необходимо найти решение этой СЛУ ( с точностью .

Итерационная схема для решения систем линейных уравнений осно­вана на приведении их к виду, удобному для итераций:

(1.9.3-2)

 

где

Эта система получена из системы (1.9.3-2) в предположении, что диагональные элементы отличны от нуля.

Обозначив через правую часть i-го уравнения, запишем СЛУ в виде:

 

(1.9.3-3)

 

Зададимся начальными приближениями корней и подставим их в правую часть уравнений системы (1.9.3-3). Получим первые приближения к корням: .

(1.9.3-4)

 

Продолжив подстановку, получим последовательность приближений:

(1.9.3-5)

 

Если существуют пределы последовательностей, то они являются решением СЛУ:

Условие сходимости метода итераций основывается на следующей теореме:

Теорема: Если в системе уравнений

(1.9.3-6)

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

Условие сходимости метода итераций можно формализовать следующим образом:

(1.9.3-7)

Оценим погрешность.В процессе решения СЛУ надо добиться выполнения условия:

(1.9.3-8)

Это условие выполняется, если

 

(1.9.3-9)

 

где норма матрицы 1.9.3-6.

 

Схема алгоритма решения систем линейных уравнений методом итерации приведена на рис. 1.9.4-1.

 

Пример 1.9.3-1. Решить систему методом итерации с точностью .

 

 

Условие сходимости (1.9.3-7) выполнено. Тогда приведем систему к виду (1.9.3-6)

 

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

	1.92	3.19	5.04
	1.9094	3.1944	5.0446
	1.90923	3.19495	5.04485

 

 

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

 

Метод Зейделя является усовершенствованным методом итераций.

Для этого необходимо исходную СЛУ привести к виду удобному для итераций

Выберем начальные приближениями корней и подставим их в правые части уравнений системы (1.9.3-4). Приближения к решению вычисляют по формулам:

(1.9.4-1)

 

При этом замещение “старых” значений неизвестных на “новые” происходит одновременно.

Для сходимости итерационного процесса достаточно выпол­нения условий

 

, или < 1, (1.9.4-2)

где -- норма матрицы.

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

, где - заданная точность.

 

Оценим погрешность.В процессе решения СЛУ надо добиться выполнения условия:

(1.9.4-3)

 

Это условие выполняется, если

(1.9.4-4)

Схема алгоритма решения систем линейных уравнений методом итерации и Зейделя приведена на рис. 1.9.4-1.

 

Рис. 1.9.4-1. Схема алгоритма методов итерации и Зейделя

 

Пример 1.9.4-1. Решить систему методом Зейделя, выполнив две итерации.

.

 

Применяем процесс Гаусса – Зейделя

 

Находим второе приближение

	1.92	3.1924	5.04465
	1.90934	3.19495	5.04481

 

Заметим, что метод Зейделя требует меньшего числа итераций при той же точности, чем метод итерации.

 

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

 

При преобразовании системы 1.9.1-1 к треугольному виду получаем следующую 1.7.3.1. Технология решения задач аппроксимации функций средствами MathCad

 

В Mathcad имеется несколько функций аппроксимации, различающихся способом "соединения" точек (прямой линией или различными кривыми).

 

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

 

Пример 1.7.3-2. Осуществить аппроксимацию таблично заданной функции многочленом 1-й, 2-й и 3-й степени.

В этом примере рассмотрено использование функции linfit(x,y,f), где x,y- соответственно векторы значений аргументов и функции, а f - символьный вектор базисных функций. Использование этой функции позволяет определить вектор коэффициентов аппроксимации методом наименьших квадратов и далее невязку - среднеквадратическую погрешность приближения исходных точек к аппроксимирующей функции (сkо). Степень аппроксимирующего многочлена задается при описании символьного вектора f. В примере представлена аппроксимация таблично заданной функции многочленом 1-й, 2-й и 3-й степени. Вектор s представляет собой набор аппроксимирующих коэффициентов, что позволяет получить аппроксимирующую функцию в явном виде.

 

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

expfit(X,Y,g) Решение ОДУ 2-го порядка вида у"=F(x, y, z), где z=y' также может быть получено методом Рунге-Кутты 4-го порядка. Ниже приведены формулы для решения ОДУ:

" регрессия экспонентой

" sinfit(X,Y,g) - регрессия синусоидой

" pwfit(X,Y,g) - регрессия степенной зависимостью

" logfit(X,Y,g) - регрессия логарифмической функцией

В этих функциях: х - вектор аргументов, элементы которого расположены в порядке возрастания; y - вектор значений функции; g - вектор начальных приближений коэффициентов a, b и с; t - значение аргумента, при котором определяется функция.

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

 

 

1.9.6. Тестовые задания по теме
«Системы линейных уравнений»