MU_LR_VychMat_230400

41

3.4.КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Что называется решением СЛАУ?

2.Каковы условия существования решения СЛАУ?

3.Каковы условия единственности решения СЛАУ?

4.В чем состоит метод Гаусса для решения систем линейных уравнений

5.В чем состоит метод LU-разложения для решения систем линейных уравнений

6.Какова вычислительная сложность метода Гаусса?

7.Какова вычислительная сложность метода LU-разложения ?

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

9. Для каких систем линейных уравнений применяется метод квадратного корня?

42

4. ЗАНЯТИЕ 3. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.

4.1.ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

4.1.1.Концепция итерационных методов решения СЛАУ

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

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

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

Простейшим итерационным методом решения СЛАУ является метод простых

многократно выполняются действия по уточнению решения согласно рекуррентному соотношению

где 0 - заданная точность, которую необходимо достигнуть при решении задачи, или более простого условия:

43

x(k 1) x(k ) .

Теорема 1. (о достаточном условии сходимости метода простых итераций)

Метод простых итераций, реализующийся в процессе последовательных приближений (3.3), сходится к единственному решению исходной системы Ax B при любом начальном приближении x(0) со скоростью не медленнее геометрической прогрессии, если какая-либо норма матрицы α меньше 1, т.е. α s 1, s 1,2,3 .

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

Условие Теорема 1, как достаточное (но не необходимое!) предъявляет завышенные требования к матрице α и поэтому сходимость иногда будет, даже если α 1.

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

достаточно, чтобы собственные значения матрицы α были по модулю меньше единицы,

т.е. i (α) 1, i 1,..., n .

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

Теорема 3. (о погрешности приближений, вычисляемых методом простых итераций)

Если в итерационном процессе норма матрицы α , согласованная с нормой вектора x , меньше единицы ( α 1), то справедлива следующая оценка погрешности:

Это соотношение может быть переписано через начальное приближение x(0) β :

На основе этого можно записать априорную оценку погрешности

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

44

достижения заданной точности:

k 1 lg lg(1 || α ||) lg β . lg || α ||

Преобразование системы Ax B к виду x = αx + β с матрицей α ,

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

1. Уравнения, входящие в систему Ax B переставляются так, чтобы выполнялось условие преобладания диагональных элементов (3.4) (для той же цели можно использовать другие элементарные преобразования). Затем, первое уравнение разрешается относительно x1 , второе - относительно x2 и т.д. При этом получается матрица α с нулевыми диагональными элементами.

Например, система

2.8x1 x2 4x3 60, 10x1 x2 8x3 10,

x1 2x2 0.6x3 20

спомощью перестановки уравнений приводится к виду

10x1 x2 8x3 10,x1 2x2 0.6x3 202.8x1 x2 4x3 60,

Теперь диагональные элементы преобладают. Выражаем неизвестные:

Заметим, что α1 max{0.9;0.8;0.95} 0.95 1, т.е. условие теоремы 3.1 выполнено.

Пример других элементарных преобразований: Пусть дана система

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

45

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

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

3)Чем меньше величина нормы α , тем выше скорость сходимости метода.

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

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

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

В развернутой форме данный процесс записывается в виде:

46

x(k 1) (E L) 1Ux(k ) (E L) 1β .

Тогда достаточное условие сходимости (Теорема 1) будет иметь вид:

α(E L) 1U 1 ,

а необходимое и достаточное (Теорема 2) :

i (α) i (E L) 1U 1.

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

Таким образом, система AT AX AT B является нормальной, а матрица AT A симметричной и положительно определенной.

4.1.4. Проверка сходимости на каждом шаге

(для метода простых итераций и метода Гаусса-Зейделя):

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

4.2. ЗАДАНИЕ НА РАБОТУ

Решить систему линейных алгебраических уравнений:

a11x1 a12x2 a13x3 b1a21x1 a22x2 a23x3 b2

a31x1 a32x2 a33x3 b3

методами:

1.Простых итераций

2.Гаусса-Зайделя

4.3. ВАРИАНТЫ ЗАДАНИЙ

см. занятие 3.

47

4.4.КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Что называется решением СЛАУ?

2.Каковы условия существования решения СЛАУ?

3.Каковы условия единственности решения СЛАУ?

4.В чем заключается основная идея итерационных методов решения СЛАУ?

5.Что понимается под сходимостью итерационных методов решения СЛАУ?

6.Каким образом можно контролировать сходимость итерационного процесса на каждой итерации?

7.В чем состоит метод простой итерации для решения систем линейных уравнений?

8.В чем состоит метод Гаусса-Зайделя для решения систем линейных уравнений?

9.Какова сложность метода простой итерации?

10.Какова сложность метода Гаусса-Зайделя?

11.Какой метод эффективнее – метод простой итерации или метод Гаусса-Зайделя?

48

5.ЗАНЯТИЕ 4. АЛГЕБРАИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ

5.1.ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

5.1.1.Постановка задачи интерполяции

Система условий (5.1) называется условиями интерполяции.

Геометрически требование выполнения условий интерполяции означает (Рисунок 5.1), что нужно найти кривую F(x), проходящую через заданную систему точек.

y F(x)

y

y f (x)

Рисунок 5.1 – Сущность интерполяции

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

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

k 0

где k (x) , k=0,1,…,n – фиксированная система базисных функций.

Для существования и единственности решения задачи интерполяции необходимо и достаточно, чтобы система базисных функций была линейно-независимой на [a,b] .

Одной из типичных линейно-независимых систем функций является система

49

называется полиномом степени n .

Интерполяция полиномом называется полиномиальной или алгебраической интерполяцией.

5.1.2. Интерполирование по Вандермонду

Интерполирование по Вандермонду заключается в нахождении коэффициентов интерполяционного полинома (5.3) путем непосредственного решения системы уравнений, составленной по условиям интерполяции.

В случае интерполяции полиномом (5.3), условия интерполяции будут иметь вид:

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

Следовательно, решение системы (5.4) существует и единственно. Тогда, решив ее любым методом решения СЛАУ можно найти искомые коэффициенты интерполяционного полинома c0 ,c1 ,...,cn .

Пример 5.1

Дана таблица значений функции y = x2 + 4x - ex .

Для узлов 0,1,3 построить интерполирующий многочлен, используя интерполирование по Вандермонду и определить с его помощью значение функции при x=0.7.

50