Введение в теорию погрешностей

1.  Введение в теорию погрешностей.

1.1.  Истоки и общая классификация погрешностей.

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

1)  математическое описание задачи (математическая модель) по сути является приближенной – т. е. в математической модели не учтены существенные факторы, присущие её реальному прообразу. Или же исходные данные задачи заданы не точно;

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

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

Погрешности, соответствующие пунктам носят названия 1) – неустранимой погрешности, 2) – погрешностью метода, 3) – вычислительная погрешность.

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

Определение: пусть а – точное задание величины, подлежащее отысканию, а* - значение этой величины, соответствующее выбранной математической модели, аh - соответствует а, получаемое посредством численного метода в рамках отсутствия погрешностей, вызванных округлениями и усечениями, аh* - приближенное значение а, полученное при реальных вычислениях. Тогда под неустранимой погрешностью понимают величину ε1 = а* - а, погрешностью метода ε2 = аh - а*, вычислительная погрешность ε3 = аh*- аh.

Определение: под полной погрешностью понимают величину ε0 = аh* - а – полная погрешность, удовлетворяющая условию ε0 = ε1 + ε2 + ε3.

Замечание: при решении конкретных задач зачастую под погрешностью того или иного типа понимают не разности ε0, и т. д., а определённые меры близости между ними, в частности, при рассмотрении скалярной величины а используют соответствующие абсолютные погрешности, определяемые соотношением: .

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

1.2.  Представление чисел в компьютерах.

Определение: пусть х – некоторое вещественное число, причём конечное, числа p, q - конечные натуральные числа. Представлением числа х в р-ичной позиционной системе счисления, где р – основание системы, называется представление этого числа в форме . (1.1.)

Замечание: наиболее часто используются позиционные системы счисления с основаниями р = 2, 3, 8, 10, 16.

Замечание: любое конечное вещественное число х может быть представлено в виде (1.1.) для любого р, которое не равно 1: .

Из представления (1.1.) следует, что в общем случае вещественное число х требует для своего представления использования бесконечной последовательности символов α1, т. д., каждый из которых является натуральным числом и лежит в границах . В рамках теоретических рассуждений это допустимо, но при проведении конкретных вычислений невозможно использовать бесконечный набор символов и выполнять бесконечное число алгебраических операций с числами из R – множество вещественных чисел. Это приводит к необходимости использования конечного множества вещественных чисел. При этом использование конечного набора чисел порождает как погрешности при вводе чисел, так и накопление погрешности в процессе вычисления.

Определение: под множеством F чисел с плавающей точкой понимаются все вещественные числа, представимые в виде (1.2.), где q – показатель степени, r – точность, р – основание, , q – любое конечное целое число.

Определение: если для любого х из множества чисел с плавающей точкой выполняется равенство, то плавающая система F называется нормализованной. Число - мантисса числа х.

Замечание: в ряде случаев числа с плавающей точкой представляют в виде , где - мантисса, q -1 – показатель степени.

Конечное множество F содержит ровно чисел, где .

1.3.  Элементы теории погрешностей.

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

Под значащими цифрами числа понимают все цифры в его записи в десятичной системе счисления, начиная с первой ненулевой слева. Например, х* = 0, 0040201 (5 цифр).

Если абсолютная погрешность числа не превосходит половины 1 разряда, выбранной значащей цифры, то эта цифра называется верной. Например, х = 58, 43; х* = 58, 40; = 0, 03 > ½ 0,01 – неверно, т. к. 3 сотых больше, чем 5 тысячных.

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

Замечание: если x* - приближенное значение числа x, а , где x* и записывается с тремя знаками после запятой.

Если известна относительная погрешность числа, то число x принято записывать .

Правило округления: для округления числа до n-значащих цифр все цифры, стоящие справа от значащей n-той цифры, или в случае необходимости сохранения разряда заменяют нулями. Кроме этого осуществляют действия:

а) если первая отброшенная цифра < 5, то оставшиеся десятичные знаки не меняются;

б) если первая отброшенная цифра > 5, то к последней оставшейся цифре прибавляется 1;

в) если первая из отброшенных цифр = 5 и среди остальных отброшенных цифр есть ненулевые, то последняя оставшаяся цифра увеличивается на 1;

г) если первая из отброшенных цифр = 5, а остальные отброшенные цифры = 0, то последняя оставшаяся цифра остаётся неизменной, если она чётна, и увеличивается на 1, если она нечётна.

Теорема: если положительное приближенное число x* имеет n верных десятичных знаков, то его относительная погрешность S(x*) не превосходит 101-n.

Корректная вычислительная задача – вычислительная задача, которая удовлетворяет условиям:

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

2.  это решение единственное.

3.  это решение устойчиво по отношению к малым возмущениям (отклонениям) входных данных.

Задача некорректна, если не выполняется хотя бы одно из этих условий.

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

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

2.  Решение уравнений с одной переменной.

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

Наиболее общий вид нелинейного уравнения F(x) = 0 (2.1.), где F(x) определена и непрерывна на конечном или бесконечном интервале [a, b].

Определение: число - корень уравнения, если функция .

Определение: число называется корнем k-той кратности, если вместе с функцией обращаются в 0 все её производные функции до k-1 порядка включительно.

(2.2.)

Определение: корень кратности 1 называется простым.

Определение: уравнения называются эквивалентными (равносильными), если множества их решений совпадают.

Замечание: нелинейные уравнения с одной переменной делятся на алгебраические и трансцендентные.

Определение: уравнение (2.1.) называется алгебраическим, если функция F(x) алгебраическая.

Путём алгебраических преобразований любая алгебраическая функция может быть приведена к многочлену n-ой степени (2.3.).

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

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

Определение: решить уравнение (2.1.) означает следующее:

1.  установить, имеет ли данное уравнение корни;

2.  определить число корней уравнения;

3.  найти значение корней уравнения с некоторой точностью.

2.2.  Отделение корней.

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

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

2.  если функция на этом отрезке строго монотонна, то этот корень единственный.

2.3.  Метод половинного деления.

Пусть на отрезке [a, b] уравнение 2.1. имеет единственный корень, F(x) непрерывна на этом отрезке. Разделим отрезок пополам точкой . Если F(c) = 0, с – корень уравнения, а если , то функция меняет знак либо на отрезке [a, c] или функция меняет знак на [c, b]. Выбираем отрезок, на котором функция меняет знак, и продолжаем его половинно делить до тех пор, пока не найдём точку = 0 или отрезок очень маленькой точности (сколь угодно малого отрезка), содержащего один корень уравнения.

Пример 2.1.: решение в пакете MathCad методом половинного деления уравнения:

1. .

2. .

3. задание функции, реализующей метод половинного деления: Div2 (f, x1, x2, e), где f – функция из левой части уравнения 1, x1 – левая координата отрезка, x2 – правая координата, e (эпсилон) – точность.

4.

5.

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

Функция, возвращающая значение корня на каждом шаге метода половинного деления, представляется в виде:

Для того, чтобы увидеть результат, нужно выполнить ещё 2 команды:

1.  вычисление матрицы, первый столбец которой содержит значение корня, а второй столбец – номер итерации: ;

2.  строим график – визуализация процесса, описанного выше: .

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

Рассмотрим уравнение х = f(x) – 2.4., равносильное уравнению 2.1. Пусть - корень данного уравнения, х0 – получаем 1-е приближение, и т. д. Повторяя данную процедуру, получим последовательность: 2.5. Последовательность эту мы называем итерационной последовательностью.

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

Теорема: если функция y = f(x) непрерывна, а последовательность 2.5. сходится, то предел последовательности 2.5. является корнем заданного уравнения 2.4.

Доказательство: пусть

- корень уравнения (2.6.)

Теорема (достаточное условие сходимости итерационного процесса): пусть уравнение х = f(x) имеет единственный корень на отрезке [a, b] и выполняются следующие условия:

1.  функция f(x) определена и дифференцируема на отрезке [a, b];

2.  все значения f(x) принадлежат [a, b];

3.  существует такое q, что производная функции , тогда итерационная последовательность 2.5. сходится при любом начальном приближении х0 из отрезка [a, b];

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

из условия 3: .

…

Рассмотрим ряд (2.8.)

(2.9.)

Ряд 2.8. сравним с (2.10)

Ряд 2.10 не превосходит ряд 2.8. (это нам даёт равенство 2.7.), ряд 2.10 сходится, как сумма бесконечно убывающей геометрической прогрессии. à Т. к. ряд сходится, его частная сумма 2.9. имеет конечный придел. , то в силу того, что функция непрерывна, в силу равенства 2.6. получаем, что - корень уравнения.

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

2.5.  Оценка погрешности метода простой итерации.

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

(2.11.)

(2.12.)

(2.13.) абсолютная погрешность n-го приближения.

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

При заданной точности процесс прекращается, если

2.6.  Преобразование уравнения к итерационному виду.

Уравнение F(x)=0 приводится к виду 2.4. следующим преобразованием: . (2.15.)

Для того, чтобы функция 2.15. удовлетворяла условиям теоремы, дифференцируем её:

(2.16.)

2.7.  Решение уравнений методом простой итерации в пакете Mathcad.

x = x – 0.5 ()

1.  задаём функцию

2.  задаем функцию в соответствии с 2.15.

3.  задаем функцию в соответствии с 2.16. .

4.  построение графиков функций f1 и F. .

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

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

5.  зададим функцию правой части

6.  = 0.

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

8.  проводим визуализацию:

9.  вывод точного значения корня .

10.  проверка .

2.8.  Метод хорд.

Задано уравнение x = f (x). Ему равносильно уравнение F (x) = 0. При x, принадлежащем какому-либо интервалу, на котором выполняется условие.

Идея метода состоит в замене кривой y = F(x) хордами, проходящими через концы отрезков, в которых функция f(x) имеет противоположные знаки. Метод хорд требует, чтобы один конец отрезка, на котором находится корень, был неподвижен (неподвижная точка). В качестве неподвижной точки выбирают обычно тот конец отрезка, для которого знак функции y = F(x) совпадает со знаком второй производной. Расчётная формула имеет вид:

.

2.9.  Метод касательной (метод Ньютона).

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

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

a.  Общие сведения и основные определения.

Рассмотрим систему, которая состоит из m линейных алгебраических уравнений с n неизвестными. (3.1.)

Система 3.1. может быть записана в матричном виде Ах = b (3.2.), где А – матрица размерности m*n.

Определение: решением системы 3.1. называется упорядоченная совокупность чисел , которая обращает все уравнения системы 3.1. в верные числовые равенства.

Определение: прямые методы решения систем ЛАУ называются методы, дающие решения системы за конечное число алгебраических операций. Если нет ошибок округления, то данные решения являются точными.

Определение: итерационными методами решения систем ЛАУ называются методы, дающие решение системы как предел последовательности приближений, вычисляемых по единообразной схеме.

b.  Метод Гаусса и его реализация в пакете Mathcad.

Рассмотрим систему ЛАУ 3.1. при условии, что матрица не вырождена. Метод Гаусса состоит в преобразовании системы 3.1. методом последовательного исключения переменных к треугольному виду, т. е. система с треугольной матрицей.

(3.4.) и т. д. Далее из системы 3.4. последовательно находятся все значения переменных.

Т. о., процесс решения системы 3.1. распадается на 2 этапа.

1. прямой ход, т. е. приведение системы 3.1. к треугольному виду 3.4.;

2. обратный ход, т. е. нахождение значений неизвестных (из системы 3.4.);

Документ системы Mathcad, решающий данную задачу состоит из блоков:

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

2)  возвращающая преобразованную к треугольному виду расширенную матрицу системы:

3)  задание функции, вычисляющее значение неизвестных, вычисленных обратным ходом в соответствии с пунктом 3.4.:

.

Пример: матрица , ,

. Проверка:

c.  Вычисление определителей.

Определитель – числовая характеристика квадратной матрицы.

Рассмотрим систему уравнений:

(3.1.’)

Решение системы 3.1. существует тогда и только тогда, когда определитель матрицы системы не равен 0, т. е. матрица не вырожденная.

В mathcad существует встроенная система, которая считает определитель, но можно также использовать следующий алгоритм:

d.  Решение систем линейных уравнений методом простой итерации.

Система:

(3.7.) преобразование точки n-мерного пространства в точку этого же пространства. Используя систему 3.6. выбираем точку в качестве начального приближения, можно построить итерационную последовательность точек n-мерного пространства (3.8.).

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

Определение: функцию , определяющую расстояние между точками x и y называют метрикой, если выполнены следующие условия:

1) ;

2) расстояние равно 0 тогда и только тогда, когда мы берём 1 точку;

3) ;

4) ;

Определение: множество с введённой на нем метрикой называется метрическим пространством.

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

Определение: пространство называется полным, если в нём любая фундаментальная последовательность сходится.

Пусть F – отображение, которое действует в метрическом пространстве E в себя с метрикой , x и y – точки пространства E, а - отображения точек x и y.

Определение: отображение F пространства E в себя называется сжимающим отображением, если существует такое число альфа, которое >0 и <1, что выполняется условие:

(3.9.)

Определение: точка x называется неподвижной точкой отображения F, если x = F(x).

Теорема (теорема о достаточных условиях сходимости итерационного процесса в n-мерном пространстве): если F – сжимающее отображение, определённое в полном метрическом пространстве, то существует единственная неподвижная точка x, такая что x = . При этом итерационная последовательность, построенная для отображения F с любым начальным элементом x0 сходится к x.

Доказательство существует в любом классическом учебнике.

В ходе доказательства показывается, что выполняется неравенство: (3.10.). Из 3.10. приняв k-тое приближение за нулевое, получим (3.11.).

Рассмотрим условие, при котором отображение 3.7. будет сжимающим. Из 3.9. видно, что это зависит от способа метризации данного пространства. При решении уравнений будем пользоваться следующими 3-мя метриками:

1. (3.12.)

2. (3.13.)

3.

Для того, чтобы отображение F, заданное в метрическом пространстве 3.7. было сжимающим, достаточно выполнения одного из условий:

1)  в пространстве с метрикой (3.15.)

2)  в пространстве с метрикой (3.16.)

3)  в пространстве с метрикой (3.17.)

Для установления момента прекращения итераций при достижении заданной точности может быть использована формула, следующая из 3.11.: (3.18.).

Алгоритм решения системы методом итерации может быть реализован следующей последовательностью действий:

1.  привести систему 3.1.’ к виду с преобладающими диагональными коэффициентами;

2.  разделить каждое уравнение на соответствующий диагональный коэффициент;

3.  проверить выполнение условий 3.15., 3.17.;

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

5.  реализовать итерационный процесс (обычно за начальное приближение берётся столбец свободных членов).

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

При решении системы линейных уравнений вычислительные формулы имеют вид:

(3.19.).

Основная идея метода Зейделя выражается при помощи формул:

,

,

…

, (3.20.)

.

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

После преобразования системы к нормальному виду получим следующий результат. Теорема (достаточное условие сходимости метода Зейделя): итерационный процесс метода Зейделя для приведённой системы (3.22.) всегда сходится к единственному решению этой системы при любом выборе начального. Для пояснения выполняем преобразования: (3.1.) равносильна (3.2.). Левую и правую части равенства 3.2. умножаем на транспонированную матрицу, получим систему: CX = D (3.21.)

Система 3.21. называется нормальной и равносильна системе 3.2.

Нормальные системы обладают свойствами:

1.  матрица системы С = A*At коэффициентов при неизвестных является симметричной;

2.  все элементы, стоящие на главной диагонали положительны > 0.

Коэффициенты рассчитываются по формулам:

(3.23.) (3.24.)

Замечание: система 3.22 равносильна системе 3.21, которая в свою очередь равносильна системе 3.2.

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

1)  ввод матрицы А – коэффициентов исходной системы и b – вектора-столбца свободных коэффициентов;

2)  приведение системы сначала к нормальному виду 3.21., а затем к приведённому виду 3.22.;

3)  задание требуемой точности решения (предыдущий пункт);

4)  циклическое выполнение итерационного процесса до достижения требуемой точности.

Документ пакета MathCad, описывающий данный алгоритм, приведён в лабораторной работе №4.

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

4.1.  Векторная запись нелинейных систем, метод простых итераций.

Пусть требуется решить систему уравнений:

(4.1.)

Где f – заданные нелинейные вещественнозначные функции n-вещественных аргументов .

Вводя следующие обозначения , мы можем записать систему (4.1.) в более компактном виде: (4.2.).

(4.2.) – уравнение относительное векторной функции f векторного аргумента x.

Начнем рассмотрение методов решения с метода простой итерации.

Пусть система (4.1.) преобразована к следующей эквивалентной нелинейной системе:

или в векторной записи: ,

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

Условия сходимости даёт следующая теорема: пусть функция и замкнутое множество таковы, что:

1.  все значения функции лежат во множестве М;

2.  существует такое q < 1, что

Тогда отображение Ф(х) имеет в М единственную неподвижную точку , последовательность сходится к точке при любом начальном приближении , которое лежит в М. справедливы следующие оценки: .

Данная теорема представляет небольшой интерес из-за громоздкости конструкции.

В случаи, когда выбрано хорошее нулевое приближение практический интерес представляет теорема: пусть функция дифференцируема в замкнутом шаре , причём существует такое q < 1, что q принадлежит интервалу (0;1) и . Тогда если и r – радиус шара таковы, что выполняется, справедлива теорема предыдущая (заключение) и множество M = S.

Метод 4.5. в развёрнутом виде: (4.6.)

Аналог метода Зейделя для нелинейного случая:

(4.7.)

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

Замечание: для того, чтобы применить метод простой итерации 4.6. или модифицированный метод Зейделя 4.7. к исходной системе 4.1. необходимо эту систему 4.1. каким-нибудь способом привести к виду 4.3. Для этого 4.2. нужно поменять местами левую и правую части, домножить на –А и привести к виду Проблема заключается в правильном подборе матрицы А.

4.2.  Метод Ньютона решения систем нелинейных уравнений.

Решаем систему 4.3., равносильной системе 4.4. будем пользоваться методом последовательных приближений. Предположим, известно k-ое приближение одного из изолированных корней векторного уравнения 4.2., тогда точное значение корня может быть записано в виде: (4.9.), где - поправка (погрешность). (4.10.). Мы можем сделать разложение, ограничиваясь линейной частью, тогда получим: (4.11.). теперь можно расписать 4.11. в развёрнутом виде:

(4.12.)

Из формул 4.11. и 4.12. видно, что под производной понимается матрица Якоби системы функций f относительно переменных x.

Матрица Якоби:

С учётом матрицы Якоби формул может быть записана в следующем виде:

(4.13.)

Если можно выразить (4.14.)

Отсюда видно, что метод Ньютона состоит в построении итерационной последовательности (4.15.).

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

4.3.  Решение нелинейных систем методами спуска.

Для того чтобы неким образом решить проблему начального приближения (получить сходимость итерационного процесса) можно использовать численные методы оптимизации. Рассмотрим систему: (4.16.). Из функций системы образуем новую функцию: (4.17.). Т. к. эта функция неотрицательна, то найдётся точка (можно не единственная) такая, что будет выполняться . Если при этом окажется, что , то точка - решение системы 4.16.

Последовательность точек -приближение к точке обычно получают по следующей рекуррентной формуле: (4.18.), где k = 0,1,2, …вектор - транспонированный

Определение: итерационный метод 4.18. называется методом спуска, если вектор транспонированный при каждом k является направлением спуска, т. е. существует такое , что , и множитель подбирается так, чтобы выполнялось условие (релаксации): .

Градиент: .

Т. о., при построении численного метода 4.18. минимизации функции нужно ответить на 2 вопроса:

1. как выбрать направление спуска?

2. как регулировать длину шага в выбранном направлении с помощью скалярного параметра – шагового множителя альфа катого?

1) при выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быстро. Из курса матанализа известно, что направление наибольшего возрастания функции в данной точке показывает её градиент в этой точке, поэтому логично принять за направление спуска вектор - антиградиент функции . Этим выбором направления спуска выделяется градиентный метод.

(4.19.)

Оптимальный шаг в направлении антиградиента – это такой шаг, при котором значение будет наименьшим в заданном направлении.

Можно рассчитывать на наиболее быструю сходимость метода 4.19., если полагать в нём (4.20.).

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

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

Главный недостаток: медленная сходимость.

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

Замечание: для разных семейств численных методов минимизации могут быть рекомендованы свои критерии остановки итерационного процесса. Например, на окончание счёта градиентным методом можно выходить, когда достаточно малым становится норма градиента.

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

Замечание: для решения n-мерной системы 4.1. следует свести задачу к решению следующей экстремальной задачи .

Алгоритм поиска экстремума с шагом, не зависящим от свойств минимизируемой функции (пример 4.1.).

Простейший вариант метода наискорейшего спуска рассмотрим на примере поиска минимума квадратической функции 2-х переменных с оврагом, полость которого определяется параметром . Если =1, то это параболоид вращения, если >1, то он вытягивается вдоль оси Оx, если <1, то растягивается вдоль оси Оy.

Построение:

1.  задаём число узлов координатной сетки N:=23;

2.  задаём дискретные переменные, используемые для нумерации узлов вдоль соответствующих координатных осей: i:=0..N, j:=0..N;

3.  задаём координаты левого нижнего и правого верхнего узлов координатной сетки xmin:=-5, xmax:=5, ymin:=-5, ymax:=5;

4.  задаём координаты узлов сетки: xi = xmin + i*(xmax-xmin)/N, yj = ymin + j*(ymax-ymin)/N;

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

6.  визуализируем функции (строим поверхность и одновременно карту уровня);

7.  зададим исходные данные: - диапазон изменения номера итерации, x0:=2, y0:=-1, f0:=f(x0,y0,1), - начальное значение шага к экстремуму;

8.  зададим функции, возвращающие значения частных производных: ;

9.  зададим функцию, которая возвращает длину градиента: ;

10.  зададим функции, возвращающие координаты нормированного единичного вектора, сонаправленного с вектором, противоположным направлению векора градиента: ;

11.  зададим параметры, используемые для определения шага: ;

12.  формулы для определения величины шага: ;

13.  зададим вектор, содержащий начальное значение координат и соответствующего значения функции: ;

14.  строим итерационный процесс в соответствии с формулой 4.19.:

.

15.  визуализируем итерационный процесс: зависимость координат от номера итерации;

16.  зависимость значений минимума функции от номера итерации;

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

Данный метод основан на квадратичной аппроксимации (приближении) минимизируемой функции в окрестности точки xk. Минимум квадратичной функции легко найти, приравнивая её градиент к 0. можно сразу же вычислить положение экстремума и выбрать его в качестве приближения к точке минимума.

Вычисляем точку нового приближения по формуле: и разлогая функцию в ряд Тэйлора в окрестности точки , получим формулу квадратической аппроксимации: (4.21), где - матрица производных второго порядка:

.

Вычислим градиент и найдём оттуда значение :

(4.22.).

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

Найдём длину шага для (4.23.) – расчетная формула для метода Ньютона.

Метод Ньютона реализуется следующей последовательностью действий:

1.  задать (произвольно) точку ;

2.  вычислять в цикле по номеру итерации

·  значение вектора градиента в точке ;

·  значение матрицы вторых производных ;

·  значение матрицы, обратной матрице вторых производных ;

·  значение шага по формуле 4.23.

3.  закончить итерационный процесс, используя условия остановки итерационного процесса;

Достоинства данного метода:

1)  для квадратической функции метод позволяет найти минимум за 1 шаг;

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

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

Недостатки: необходимость вычислений и обращения матриц вторых производных. Обращение – нахождение обратной матрицы. Расходуется машинное время, могут появиться значительные погрешности, если матрица плохо обусловлена.

Замечание: в качестве количественной характеристики обусловленности матрицы (cond A) принимают произведение , где - норма матрицы, определяемая по аналогии с нормой (метрикой) вектора. , .