Вопрос 2 Численные методы решения линейных и нелинейных уравнений

Вопрос 2 Численные методы решения линейных и нелинейных уравнений

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

Рассмотрим методы численного решения уравнений и систем уравнений:

или

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

Покажем, как можно решить изначальную систему уравнений, не прибегая к оптимизационным методам. В случае, если наша система представляет собой СЛАУ, целесообразно прибегнуть к таким методам, как метод Гаусса или метод Ричардсона. Однако всё же будем исходить из предположения, что вид функции неизвестен, и воспользуемся одним из итерационных методов численного решения. Среди большого разнообразия таковых выберем один из наиболее известных — метод Ньютона. Этот метод в свою очередь основывается на принципе сжимающего отображения.

Сжимающее отображение

Сжимающее отображение — отображение метрического пространства в себя, уменьшающее расстояние между любыми двумя точками не менее чем в раз

Говорят, что функция осуществляет сжимающее отображение на , если

Тогда справедлива следующая теорема (Теорема Банаха (принцип сжимающих отображений)):

Если φ – сжимающее отображение на [a, b], то:

1. Уравнение x = φ (x) имеет единственный корень x^* в [a, b];

2. Итерационная последовательность x_i₊₁ = φ (x_i) сходится к этому корню;

3. Для очередного члена x_n справедливо

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

Общий алгоритм последовательных приближений

Уравнение f(x)=0 преобразуется к уравнению с тем же корнем вида x = φ (x), где φ (x) — сжимающее отображение.

1. Задаётся начальное приближение и точность

2. Вычисляется очередная итерация

· Если , то и возврат к шагу 3.

· Иначе и остановка.

Применительно к общему случаю операторных уравнений этот метод называется методом последовательных приближений или методом простой итерации. Однако уравнение f(x)=0 можно преобразовывать к сжимающему отображению x=φ (x), имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.

Локальная и глобальная интерполяция

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

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

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

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

Кусочно-квадратичная интерполяция

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

, при (8)

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

(9)

Из системы уравнений (9) можно найти коэффициенты:

(10)

Рис.2. Кусочно-квадратичная интерполяция

Многочлен Лагранжа

При глобальной интерполяции на всем интервале строится единый многочлен. Одной из форм записи интерполяционного многочлена для глобальной интерполяции является многочлен Лагранжа:

(11)

где – базисные многочлены степени n:

(12)

То есть многочлен Лагранжа:

(13)

Многочлен удовлетворяет условию . Это условие означает, что многочлен равен нулю при каждом кроме , то есть – корни этого многочлена. Таким образом, степень многочлена равна n и при в сумме обращаются в нуль все слагаемые, кроме слагаемого с номером , равного .

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

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

Кусочно-линейная и кусочно-квадратичная локальные интерполяции являются частными случаями интерполяции многочленом Лагранжа.

Пример:

Найдем формулу интерполяции для f(x) = tan(x) имеющей следующие значения:

Получим

Многочлен Ньютона

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

Разделенные разности нулевого порядка совпадают со значениями функции в узлах. Разделенные разности первого порядка определяются через разделенные разности нулевого порядка:

(14)

Разделенные разности второго порядка определяются через разделенные разности первого порядка:

(15)

Разделенные разности k-го порядка определяются через разделенную разность порядка :

(16)

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

(17)

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

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

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

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

Разностная схема — это конечная система алгебраических уравнений, поставленная в соответствие какой-либо дифференциальной задаче, содержащей дифференциальное уравнение и дополнительные условия (например краевые условия и/или начальное распределение).

Рассмотрим дифференциальное уравнение, заданное в некоторой области D, ограниченной контуром Г:

LU = f, (9.2)

где U - решение (9.2). Множество D_h ={M_h} состоящее из изолированных точек M_h, принадлежащих замкнутой области D, называется сеткой, а точки M_h - узлами сетки. Функция, определенная в узлах сетки, называется сеточной функцией U_h_.На практике, как правило, можно вычислить только приближенное сеточное значение функции U^(h).

Для нахождения U^(h) строим систему численных уравнений:

L_h(U^(h)) = f^(h), (9.3)

где L_h – разностный оператор, соответствующий оператору L, f^(h) – разностный аналог правой части.Уравнение (9.3) является разностной схемой.

Таким образом, в методе сеток происходит замена пространства V (пространства непрерывных в D функций U) на пространство V_h (пространство, образованное совокупностью сеточных функций U_h, определенных на D_h.). В линейных пространствах V_h и F_h введем нормы и , которые являются сеточными аналогами норм в пространстве V и F.

Сходимость

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

Определение. Говорят, что разностная схема (9.3) является сходящейся, если при h ® 0 выполняется условие

. (9.4)

Если выполнено условие (с=const, s> 0), то говорят, что имеет место сходимость со скоростью порядка s.

Аппроксимация

Аппроксимация – это приближение. Приближение чего-то к чему-то с той или иной точностью.

Определение. Говорят, что разностная схема (9.3) аппроксимирует задачу (9.2) на решение U , если

L_h(U_h ) = f^(h)+d f^(h) (9.5)

при h ® 0,

величина d f^(h) называется погрешностью аппроксимации.

Если (M=const, β > 0), то говорят, что разностная схема (9.3) аппроксимирует задачу (9.2) с погрешностью порядка β относительно h.

Устойчивость

Усто́ йчивость — способность системы сохранять текущее состояние при влиянии внешних воздействий.

Определение. Разностная схема (9.3) называется устойчивой, если существует такое h₀> 0, что для всех h< h₀ и любых f^(h)Î F_h выполняются условия:

1) разностная схема (9.3) имеет единственное решение;

2) , где M – постоянная, не зависящая от h и f^(h).

Теорема. Пусть разностная схема L_h(U^(h)) = f^(h) аппроксимирует задачу LU = f на решение U с порядком s> 0 относительно h и устойчива. Тогда эта схема будет сходящейся и порядок ее сходимости будет совпадать с порядком аппроксимации, т. е. будет справедлива оценка:

, (9.6)

где с – постоянная, не зависящая от h.

ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

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

В данном разделе рассматриваются методы решения одномерных задач оптимизации вида

R(x) -> max, , где х — скаляр, а и b — соответственно нижняя и верхняя граница значения переменной x.В основном рассматриваются алгоритмы, связанные с построением улучшающей последовательности. Решением задачи называется х*, при котором R(x*) > R(x) для любого значения . При практическом решении задач не будем различать два значениях и , ecли , где — задаваемая погрешность решения.

Метод сканирования

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

Достоинство метода в том, что можно найти глобальный максимум критерия, если R(x) — многоэкстремальная функция. К недостаткам данного метода относится значительное число вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.

Метод деления пополам

Метод основан на делении текущего отрезка [a, b], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на / 2, где — погрешность решения задачи оптимизации. Если R(x + /2) > R(x - /2), то максимум располагается на правой половине текущего отрезка [а, b],

в противном случае — на левой.

Иллюстрация метода половинного деления

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

Пример. Дана функция R(x) = 100*sin(x+1). Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0, 05.Результаты расчетов. Середина отрезка х= 0, 5, значение критерия R =99.75, значение R(0, 5 - /2) =R(0, 475) = 97.92, значение R(0, 5 + /2) =R(0, 525) =99.89. Следовательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является [0, 5, 2J.

Метод золотого сечения

Метод основан на делении текущего отрезка [a, b], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум.

Иллюстрация метода золотого сечения.

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

Если ab=1, ad=x, тогда x=0.38197

Путем сравнения R(c) и R(d) определяют следующий отрезок, где содержится максимум. Если R(d) > R(c), то в качестве следующего отрезка выбирается отрезок [a, c],

Если же R(d) < R(c), то — отрезок [a, c].

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка c и в том и другом случаях входит в интервал поиска. Поэтому на каждой следующей итерации (кроме " запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R(x), которую нетрудно получить:

Условие окончания поиска — величина отрезка, содержащего максимум, меньше заданной погрешности.

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

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

Пример. Дана функция R(x)=sin(x+1). Найти максимум на интервале: [-1, 2]. Ошибка задается по х: e =0, 05.

Результаты расчетов. Для " запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]: x1 =0, 146, x2 =0, 854.

Значения критериев в этих точках соответственно R(x1) =0, 911, R(x2 =0, 960. Следовательно, новым отрезком является [0, 146, 2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет x3 =0, 583, a R(x3) =0, 999

Столбцовые диаграммы

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

Столбцовые диаграммы — лишь один из многих типов графиков, которые может строить система MATLAB. Особенно часто столбцовые диаграммы используются при представлении данных финансово-экономических расчетов.

Рис. 3.4 дает также представление о меню Tools (Инструменты) окна графики, появившемся начиная с версии MATLAB 5.3.1 (выпуск 11.1). Нетрудно заметить, что кроме возможности вывода инструментальной панели здесь имеется целый ряд других команд, которые будут рассмотрены в дальнейшем. Это команды вывода свойств графических объектов, изменения масштаба графика, добавления осей и т. д.

Рис. 3.4.Построение столбцовой диаграммы значений элементов вектора

Построение трехмерных графиков

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

» [X.Y]=meshgrid(-5: 0.1: 5);

» Z=X.*sin(X+Y);

» meshc(X.Y, Z)

Окно с построенным графиком показано на рис. 3.5.

Рис. 3.5.Окно с графиками поверхности и ее проекции на плоскость под фигурой

Вращение графиков мышью

Можно поворачивать построенную фигуру мышью и наблюдать ее под разными углами. Рассмотрим эту возможность на примере построения логотипа системы MATLAB — мембраны. Для этого, введя команду membrane, получим исходный график, представленный на рис. 3.6.

Рис. 3.6.Построение мембраны — логотипа системы MATLAB

Контекстное меню графиков

Для переключения в режим редактирования графика нужно щелкнуть на кнопке Edit Plot (Редактировать график) с изображением курсора-стрелки. В этом режиме графиком можно управлять с помощью контекстного меню, вызываемого щелчком правой кнопки мыши. Вид этого меню при курсоре, расположенном в области трехмерного графика вне построенных трехмерных графических объектов, показан на рис. 3.8. С помощью мыши можно также выделить график. Щелчок левой клавишей выводит рамку вокруг рисунка (см. рис. 3.8). Теперь на график можно наносить стрелки, поясняющие надписи (кнопка с буквой А) и т. д.

Рис. 3.8.График в состоянии редактирования и контекстное меню