Приведение системы линейных уравнений к виду, удобному для итераций

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

или

 .

Таким образом, для сходимости вышеуказанных итерационных процессов достаточно, чтобы значения элементов a_ij при i ¹ j были небольшими по абсолютной величине. Это равносильно тому, что если для линейной системы АХ = В модули диагональных коэффициентов каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов), то итерационные процессы для этой системы сходятся, т.е. мы имеем систему

.

Причем, если  то процессы последовательных приближений и Зейделя для данной системы сходятся. Применяя элементарные преобразования, линейную систему АХ = В можно заменить такой эквивалентной системой Х = р + aХ, для которой условия сходимости будут выполнены.

ЛЕКЦИЯ 5. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

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

если обозначить левую часть за , то получим уравнение  .

Совокупность нескольких уравнений с несколькими неизвестными называют системой уравнений.

Итерационные методы решения нелинейных уравнений

А). Метод простой итерации.

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

б). Метод деления отрезка пополам (Дихотомии).

Для  :

1. находим  ;

2. вычисляем  ;

3. если , задаем , иначе .

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

Число итераций при использовании этого метода

 .

в). Метод Хорд.

Пусть имеем уравнение  , где  - непрерывная функция на  , имеющая непрерывные  и  .

Корень считается отделенным и находится на отрезке  , т.е.

Уравнение хорды проходящей через точку А₀ и В (см. рис.5.1, рис.5.2)

Рис. 5.1

Рис. 5.2

имеет вид

 .

Найдем  х = х_1, для которого  y = 0

 .

Если корень нас не устраивает, то мы находим

 ;

 ;

. . .

 .

Рассмотрим случай, когда первая и вторая производные имеют разные знаки. (рис.5.3):

,  .

Рис. 5.3

 ,

 ,

. . .

 .

Неподвижными концами отрезка является тот, для которого знак функции совпадает со знаком второй производной .

Г). Метод Ньютона.

Пусть корень уравнения f(x) = 0 отделен на отрезке [a, b], причем  и   непрерывны и сохраняют постоянные значения на всем отрезке       [a, b].

Геометрический смысл метода Ньютона в том, что дуга кривой y = f(x) заменяется касательной к этой кривой.

Первый случай (рис.5.4):

f(a) < 0 , f(b) > 0 , > 0 , > 0(основная линия)

или

f(a) > 0 , f(b) < 0 , < 0 , < 0(пунктирная линия) .

Рис. 5.4

Проведем касательную к кривой y = f(x)  в точке B₀

 .

Полагая y = 0 , x = x_{1 ,} получим

 _,

 ,

. . .

 ^.

Второй случай (рис. 5.5):

f(a) < 0 , f(b) > 0 , > 0 , < 0(основная линия)

или

f(a) > 0 , f(b) < 0 , < 0 , > 0(пунктирная линия),

.

Рис. 5.5

Полагая y = 0 , х = х₁, получим

 _,  , . . . ,  ^.

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

 , a = x_{0 .}

д). Модифицированный метод Ньютона.

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

 ,  .

Следовательно, итерационная формула имеет вид

 .

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

Метод Рыбакова

Можно рассматривать этот метод как модификацию метода Ньютона. При замене  некоторым числом , где  – значение х на [a, b] , при котором производная максимальна.

При  сходимость не нарушается, но замедляется.

Метод Рыбакова удобен для поиска всех корней уравнения f(x) = 0 на [a,b] .

1. Задаем начальные значения х = х₀ = а .

2. Для каждой последовательной итерации ( n = 0, 1, 2, …) вычисляем

и проверяем условие x_n < b, если оно выполняется, то, значит, найдены все корни, в противном случае проверяем выполнение условия . Если оно не выполняется, то повторяем цикл с пункта 2  и переходим к пункту 3.

3. Задаем начальное приближение     и снова идем на пункт 2.

Метод наискорейшего спуска

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

 .

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

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

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

так как

и

 .

Обозначим  через  , т.е.

 .

Предположим, что  . Учитывая, что , вычислим   :

,

 .

ЛЕКЦИЯ 6. ИНТЕРПОЛИРОВАНИЕ И ЭКСТРАПОЛИРОВАНИЕ

1. Математическая постановка задачи интерполирования.

В экономике и технике, часто приходится сталкиватьcя с необходимостью вычисления значений функции у = f(х) в точках, отличных от значения аргумента, фиксированных в таблице.

Подобные задачи практики формализуются как математические задачи интерполирования.

Пусть на отрезке [a, b]  задана функция у = f(х) своими n + 1 значениями ; ; … ;  в точках x₀, x₁, …, x_{n ,}  которые назовем узлами интерполяции.

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

т.е.

; ; … ; .

Процесс вычисления значений функций в точках х, отличных от узлов интерполяции, называется интерполированием функции f(х).

Если аргумент х находится за пределами отрезка интерполирования    [x₀ , x_n], то задача определения значения функции в точке х называется экстраполированием.

Задача становится однозначной, если в качестве интерполирующей функции f(х) для функции у = f(х), заданной своими n+1 значениями, выбрать многочлен F_n (x) степени не выше n, такой, что

; ; … ;  .

Многочлен F_n(x) удовлетворяющий этим условиям, называют интерполяционным многочленом, а соответствующие формулы – интерполяционными.

В случае, когда F(x) выбирается в классе степенных функций, интерполяция называется параболической.

При интерполировании возникает ряд задач:

1. Выбор наиболее удобного способа построения интерполяционной функции для каждого конкретного случая.

2. Оценка погрешности при замене f(x) интерполирующей функцией F(x) на отрезке [a, b].

3. Оптимальный выбор узлов интерполяции для получения минимальной погрешности.