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

1

Размещено на http://www.allbest.ru/

1. Об истории возникновения предмета «Численные методы»

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

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

Вычислительная математика = ЭВМ + Численные методы

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

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

1) Описание математической модели задачи на основе физической или экономической модели.

2) Изучение методов решения поставленной математической модели задачи и создание новых методов.

3) Выбор метода решения задачи исходя из заданной точности решения и особенностей задачи.

4) Составление блок-схемы программы для решения задачи на ЭВМ.

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

6) Решение задачи на ЭВМ, построение графиков, получение оценки погрешностей, обоснование результатов.

Решение нелинейных уравнений

Нелинейными уравнениями называются уравнения вида

. (1)

Здесь - нелинейная функция:

нелинейная алгебраическая функция вида

 ;

трансцендентные функции - тригонометрические, обратные тригонометрические, логарифмические, показательные и гиперболические функции;

комбинирование этих функций .

Решением нелинейного уравнения (1) является такая точка , которая при подстановке в уравнение (1) обращает его в тождество. На практике не всегда удается подобрать такое решение. В этом случае, решение уравнения (1) находят с применением приближенных (численных) методов. Тогда решением нелинейного уравнения (1) будет являться такая точка , при подстановке которой в уравнение (1) последнее будет выполняться с определенной степенью точности, т.е. , где - малая величина. Нахождение таких решений и составляет основу численных методов и вычислительной математики.

Решение нелинейных уравнений распадается на два этапа: отделение корней уравнений и уточнение корней нелинейных уравнений.

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

Первый способ отделения корней - графический. Исходя из уравнения (1), можно построить график функции . Тогда точка пересечения графика с осью абсцисс является приближенным значением корня. Если имеет сложный вид, то представим ее в виде разности двух функций . Так как , то выполняется равенство . Построим два графика , . Значение - приближенное значение корня (Рис.1), являющееся абсциссой точки пересечения двух графиков.

1

Размещено на http://www.allbest.ru/

Пример 1. Пусть дано нелинейное уравнение вида . Решим его графическим методом. Для этого представим уравнение в виде , где

; .

Графики функций ; представлены на Рис.2, из которого видно, что исходное уравнение имеет единственный корень .

1

Размещено на http://www.allbest.ru/

Пример 2. Пусть задано нелинейное уравнение вида или . Построив два графика функций и , видим, что исходное уравнение не имеет корней (Рис.3).

1

Размещено на http://www.allbest.ru/

Пример 3. Для нелинейного уравнения вида с помощью аналогичных преобразований и построений получим, что исходное уравнение имеет несколько (три) корней (Рис.4).

Второй способ отделения корней нелинейных уравнений - аналитический. Процесс отделения корней нелинейных уравнений основывается на следующих теоремах.

Теорема 1. Если функция непрерывна на отрезке и меняет на концах отрезка знак (т.е. ), то на содержится хотя бы один корень.

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

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

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

Одним из методов уточнения корня на отрезке является метод половинного деления (метод дихотомии).

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

Для уточнения корня нелинейного уравнения (1) на отрезке , где , а производная сохраняет знак, разделим отрезок пополам и исследуем знак функции в полученной точке , где . Из двух отрезков и выбираем тот, на котором функция меняет знак. Уменьшая новый отрезок в два раза, повторяем процесс и т.д. Получим последовательность отрезков , на концах которых выполняется неравенство , где . Последовательность является монотонной неубывающей ограниченной последовательностью; а - монотонной невозрастающей ограниченной последовательностью. Следовательно, существует предел:

.

Тогда .

до тех пор, пока не будет получен корень с заданной точностью.

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

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

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

(2)

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

Корень можно вычислить с заданной точностью по итерационной формуле

(3)

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

, (4)

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

1.3 Геометрическая интерпретация метода простых итераций

1

Размещено на http://www.allbest.ru/

Построим два графика: и . Абсцисса точки пересечения графиков - корень . Построим итерационный процесс. Зададим . Вычислим - первое приближение и - второе приближение. В первом случае (Рис.5) процесс сходящийся (). Во втором случае (Рис.6) процесс расходящийся ().

Приведение нелинейного уравнения к виду , допускающему сходящиеся итерации.

1

Размещено на http://www.allbest.ru/

Выполнение условия сходимости можно добиться путем перехода от исходного уравнения к эквивалентному виду следующим образом: умножим обе части уравнения (1) на , затем прибавим к обеим частям по , тогда . Обозначим , тогда . Константа выбирается так, чтобы выполнялось достаточное условие сходимости итерационного процесса (4), т.е. . Это условие равносильно , отсюда при и при .

Требуемую точность вычислений можно обеспечить путем использования оценок приближения к корню :

1) ; 2)

1

Размещено на http://www.allbest.ru/

При второе неравенство примет вид . Таким образом, если , то . Очевидно, что чем меньше , тем быстрее сходится процесс итераций. Практически грубую оценку приближенного решения можно получить без дополнительных вычислений при . В этом случае (Рис.7) итерации попеременно оказываются то с одной, то с другой стороны корня, так что корень заключен в интервале . Это надежная, хотя и грубая оценка, но она неприменима при , когда итерации сходятся к корню монотонно, т.е. с одной стороны. Вблизи корня итерации сходятся примерно так же, как геометрическая прогрессия со знаменателем . Чтобы сумма дальнейших членов прогрессии не превосходила , должен выполняться критерий сходимости

.

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

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

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

Недостатки методов:

- трудность приведения уравнения (1) к виду (2).

- если начальное приближение далеко от корня, то число итераций достаточно большое. Объем вычислений возрастает.

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

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

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

Пример. Методом итераций найти корни уравнения .

1

Размещено на http://www.allbest.ru/

Для нахождения интервала расположения корней воспользуемся графическим методом. Для этого преобразуем исходное уравнение к виду и построим два графика и (Рис.8). Абсцисса точки пересечения этих графиков является приближенным значением корня . Более точные значения можно получить по итерационной формуле (3). Из рисунка видно, что корень находится на отрезке . Выберем ; , . На концах отрезка функция меняет знак на .

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

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

.

1.4 Метод Ньютона (метод касательных)

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

(5)

1

Размещено на http://www.allbest.ru/

Геометрически (Рис.9) этот процесс означает замену на каждой итерации графика кривой касательной к ней в точках .

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

(6)

При произвольном начальном приближении итерации сходятся, если

.

Метод Ньютона рекомендуется применять для нахождения простых действительных корней уравнения (1).

Достоинством метода является то, что он обладает быстрой скоростью сходимости, близкой к квадратичной. Недостатки метода:

- не при любом начальном приближении метод Ньютона сходится, а лишь при том, для которого .

- если , то .

- если , то .

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

.

2. Решение систем нелинейных уравнений

Система нелинейных уравнений имеет вид:

(7)

Здесь - неизвестные переменные, а система (7) называется нормальной системой порядка , если хотя бы одна из функций нелинейна.

Решение систем нелинейных уравнений - одна из трудных задач вычислительной математики. Трудность состоит в том, чтобы определить: имеет ли система решение, и, если - да, то сколько. Уточнение решений в заданной области - более простая задача.

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

2.1 Метод простых итераций для решения систем нелинейных уравнений

Из исходной системы (7) путем эквивалентных преобразований переходим к системе вида:

 (8)

Итерационный процесс, определяемый формулами

,

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

или .

Распишем первое условие:

при

при .

Распишем второе условие:

при

при .

Рассмотрим один из способов приведения системы (7) к виду (8), допускающему сходящиеся итерации.

Пусть задана система второго порядка вида:

.

Требуется привести ее к виду:

.

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

где .

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

где .

Неизвестные постоянные определим из достаточных условий сходимости

и .

Запишем эти условия более подробно:

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

.

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

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

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

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

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

(9)

где

Трудности при использовании метода Ньютона:

существует ли обратная матрица?

не выходит ли за пределы области ?

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

(10)

Но ответа на второй вопрос, модифицированный метод Ньютона не дает.

Итерационный процесс по формулам (8) или (10) заканчивается, если выполняется следующее условие

.

Достоинством метода Ньютона является его быстрая сходимость по сравнению с методом простых итераций.

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

Пусть дана система линейных алгебраических уравнений (СЛАУ) вида

(11)

или в матричной форме

. (12)

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

Рассмотрим решение этой системы методом простых итераций. Для применения этого метода необходимо предварительно преобразовать систему (12) к виду

, (13)

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

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

(14)

или в координатной форме:

(15)

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

Пусть , тогда, переходя к пределу в равенстве (14), имеем

или имеет место формула (13). Следовательно, вектор - решение системы.

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

.

Рабочая формула итерационного процесса имеет в этом случае следующий вид:

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

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

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

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

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

.

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

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

4. Интерполирование функций

Задача интерполяции функций возникает в тех случаях, когда:

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

известна лишь таблица функции и требуется определить ее аналитическое выражение;

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

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

4.1 Интерполяционная формула Лагранжа

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



			…
			…

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

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

Здесь в каждом слагаемом отсутствует скобка , которой соответствует коэффициент .

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

При : .

.

Следовательно, коэффициент вычисляется по следующей формуле:



При : .

.

Следовательно, коэффициент вычисляется по следующей формуле:

.

Значения остальных коэффициентов вычисляются аналогично.

С учетом найденных коэффициентов интерполяционный многочлен Лагранжа запишется в виде

Остаточный член формулы:

,

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

Пример. По заданной системе точек



	0.5	0.707	1.0

построить интерполяционный многочлен Лагранжа второго порядка вида:

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

Тогда многочлен Лагранжа второго порядка будет иметь вид:

.

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

и .

Погрешность вычислений, по сравнению с истинным значением, составляет

.

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

4.2 Первая интерполяционная формула Ньютона

Если таблица, для которой построена формула Лагранжа, задана для равноотстоящих узлов , то формула Лагранжа упрощается. Обозначим через . Тогда

;

;…, .

С учетом введенных обозначений формула Лагранжа запишется так:

.

Запишем формулу Лагранжа в случае, если :

.

Получили формулу линейной интерполяции вида.

.

Здесь - табличные разности первого порядка.

При получаем формулу квадратичной интерполяции вида

.

Здесь - табличные разности второго порядка.

Таким образом, первая интерполяционная формула Ньютона будет иметь вид:

.

Остаточный член формулы имеет вид:

, где ,

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

4.3 Вторая интерполяционная формула Ньютона

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

.

Погрешность формулы имеет тот же смысл, что и в первой формуле Ньютона.

4.4 Применение интерполяционных многочленов для приближенного вычисления производных функции

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

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

Более точные значения производных можно получить, если предположить, что . Тогда получим:

.

Аналогично можно получить и т.д.

4.5 Численное интегрирование. Квадратурная формула Ньютона-Котеса

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

(16)

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

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

Рассмотрим способы вычисления однократных интегралов.

Если воспользоваться интерполяционным полиномом Лагранжа, то, заменяя функцию полиномом , получим равенство

(17)

где - ошибка этой квадратурной формулы.

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

(18)

Выведем явные выражения для коэффициентов формулы (18). Многочлен Лагранжа имеет коэффициенты

, .

Вводим обозначения и и с учетом этих обозначений многочлен Лагранжа запишем в виде:

(19)

Заменяя в формуле (18) функцию полиномом в виде (19), получим:

,

где .

Так как и , то сделав замену переменных в определенном интеграле, будем иметь:

, .

Так как , то можно записать коэффициенты Котеса:

, (20)

Квадратурная формула при этом принимает вид:

(21)

Рассмотрим частные случаи.

По формуле (20) при вычислим:

,

.

Полученная формула является формулой трапеций для приближенного вычисления определенного интеграла (Рис.10).

По формуле (20) при вычислим:

;

.

Следовательно, так как , то квадратурная формула для вычисления интеграла имеет вид

.

1

Размещено на http://www.allbest.ru/

1

Размещено на http://www.allbest.ru/

Эта формула является формулой Симпсона. Геометрическая интерпретация формулы состоит в том, что происходит замена данной кривой параболой , проходящей через три точки (Рис.11).

4.7 Метод наименьших квадратов для обработки результатов экспериментов

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

.

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



			…
			…

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

Используя вид , получим:

.

Необходимыми условиями экстремума функции является равенство нулю ее первой производной по всем переменным . Расписав эти условия, получим СЛАУ вида:

Запишем систему для определения в нормальной форме:

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

Запишем алгоритм метода наименьших квадратов.

Вводим таблицу чисел .

Вычисляем .

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

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

.

Для этого необходимо вычислить следующие суммы

и решить СЛАУ относительно неизвестных коэффициентов вида:

Значения неизвестных коэффициентов равны:

.

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

.

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

.

5. Решение обыкновенных дифференциальных уравнений и систем

численный уравнение интеграл функция

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

Методы их решения подразделяются на два класса:

аналитические методы, в которых решение получается в виде аналитических функций;

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

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

Решить дифференциальное уравнение

(16)

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

.

Рассмотрим три наиболее распространенных при решении практических задач численных метода интегрирования Эйлера, Рунге-Кутта и Адамса.

5.1. Метод Эйлера

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

Пусть дано дифференциальное уравнение с начальными условиями (задача Коши)

(17)

и удовлетворяются условия существования и единственности решения.

Требуется найти решение задачи Коши (17) на отрезке . Находим решение в виде таблицы . Для этого разобьем отрезок на равных частей и построим последовательность где - шаг интегрирования. Проинтегрируем исходное уравнение на отрезке :

Полученное соотношение можно переписать так

(18)

Если считать подинтегральную функцию постоянной на участке и равной значению в начальной точке этого интервала , то получим

Подставляя полученный результат в формулу (18) получаем основную расчетную формулу метода Эйлера:

(19)

Вычисление значений осуществляется с использованием формулы (19) следующим образом. По заданным начальным условиям и полагая в выражении (19) вычисляется значение

(20)

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

(21)

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

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

Метод Эйлера может быть применен к решению систем дифференциальных уравнений.

Пусть задана система двух уравнений первого порядка

(22)

с начальными условиями

.

Необходимо найти решение этой задачи Коши. Проводя аналогичные рассуждения, получаем расчетные формулы вида:

(23)

где - шаг интегрирования.

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

5.2 Метод Рунге-Кутта

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

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

Выражение (18) можно переписать в виде:

(24)

где - приращение искомой функции на -ом шаге интегрирования.

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

Перенося первое слагаемое в этой сумме в левую часть получим, что

(25)

Здесь производные определяются последовательным дифференцированием уравнения (16).

Вместо непосредственных вычислений по формуле (25) в методе Рунге-Кутта для каждого значения определяются четыре числа:

(26)

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

. (27)

Формула Рунге-Кутта имеет погрешность .

Таким образом, рабочая формула Рунге-Кутта для интегрирования

.

В отличие от расчетной схемы метода Эйлера, в которой каждое следующее значение вычисляется непосредственно по единой формуле (19), в методе Рунге-Кутта необходимо проведение промежуточных вычислений по формулам (26) и (27).

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

(28)

Где

(29)

Приближенное интегрирование системы уравнений (22) осуществляется по формулам вида:

(30)

5.3 Метод Адамса

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

Вычислим величины , , , .

Метод Адамса позволяет найти решение задачи - функцию - в виде таблицы функций. Продолжение полученной таблицы из четырех точек осуществляется по экстраполяционной формуле Адамса:

Затем уточнение проводится по интерполяционной формуле Адамса:

.

Метод Адамса легко распространяется на системы дифференциальных уравнений. Погрешность метода Адамса имеет тот же порядок, что и метод Рунге-Кутта.

5.4 Применение дифференциальных уравнений с малым параметром для решения нелинейных трансцендентных и алгебраических уравнений

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

(31)

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

дискретные схемы решения.

непрерывные схемы решения.

Дискретные схемы решения были рассмотрены выше. Заметим, что основными недостатками вышеперечисленных методов являются:

зависимость от начальных условий или от интервала нахождения корня;

сравнительно низкая скорость сходимости;

ничего не говорится о правилах перехода от корня к корню уравнения (31) в случае, если их несколько.

При применении непрерывных схем для решения уравнения (31) процесс нахождения корней осуществляется путем решения соответствующего обыкновенного дифференциального уравнения

(32)

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

(33)

если этот предел существует. Обозначим через решение задачи Коши (33), - искомое решение уравнения (31). Тогда должно иметь место тождество . Вводя обозначение для отклонения и вычитая из (33) последнее уравнение имеем

. (34)

Разлагая в ряд Тейлора в окрестности точки с сохранением линейных членов и подставляя полученное выражение в (34), получаем дифференциальное уравнение в отклонениях , решение которого имеет вид

(35)

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

(36)

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

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

Перепишем уравнение (31) в виде

(37)

где - малый параметр, .

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

(38)

если этот предел существует.

Проводя рассуждения, аналогичные рассуждениям, приведенным выше, получим, что решение уравнения (37) в точке будет иметь вид:

(39)

При этом, так как , то условие сходимости (36) останется прежним.

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

,

.

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

6. Краевые задачи для дифференциальных уравнений второго порядка

Пример 1. Рассмотрим простейшую двухточечную краевую задачу.

Найти функцию , удовлетворяющую дифференциальному уравнению второго порядка вида:

(40)

и принимающую при и заданные значения . Геометрически (Рис.10) это означает, что требуется найти интегральную кривую, проходящую через данные точки и .

Пример 2. Найти такое решение дифференциального уравнения (40), чтобы производные имели заданное значение . Геометрически (Рис.11) это сводится к отысканию интегральной кривой, пересекающей прямые и под заданными соответственно углами и такими, что и .

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

Рассмотрим двухточечную краевую задачу для линейного дифференциального уравнения. Найти решение уравнения

(41)

с дополнительными краевыми условиями

 (42)

где числа считаются известными и

,

то есть одна из величин не равна нулю.

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

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

.

Складываем эти ряды и получаем выражение второй производной в конечно-разностной форме:

.

Аналогично получим формулу для первой производной, если вычтем ряды:

.

Обозначим: . .

С учетом введенных обозначений запишем исходное уравнение для узловых точек :

, (43)

Представим

;

;

в конечно-разностной форме, тогда к системе (43) добавляется еще два уравнения, соответствующие краевым условиям:

(44)

(45)

Получили систему линейных алгебраических уравнений (43) - (45) с неизвестными . Решив эту систему любым известным методом, получим приближенное решение для исходной задачи.

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

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

Запишем систему (45) в канонической форме:

,

, .

Получим:

, . (46)

Будем искать в виде:

. (47)

где коэффициенты требуется определить. Выразим и подставим в исходную систему (46):

.

Выразим из последнего выражения :

.

Сравнивая полученную формулу с (47), получим выражения для :

(48)

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

Итак, вычисления, называемые прямым ходом, осуществляют в следующем порядке:

1. Вычисляют значения .

2. Находят .

3. Вычисляют , .

Обратный ход вычислений состоит в следующем:

1. Решают систему из двух уравнений относительно и :

и получают .

2. Вычисляют , начиная с и далее до .

3. Находят .

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

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

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

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

(49)

где - независимые переменные, - искомая функция, - первые и вторые частные производные по аргументам и .

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

7.1 Метод сеток для уравнения параболического типа

В качестве примера уравнения параболического типа остановимся на уравнении теплопроводности для однородного стержня длиной :

(50)

где - температура и - время. Будем предполагать, что . То есть от уравнения (50) перейдем к уравнению

(51)

Пусть задано распределение температуры в начальный момент времени и законы изменения температуры в зависимости от времени на концах стержня и :; . Требуется найти распределение температуры вдоль стержня длиной в любой момент времени . Функция должна быть непрерывна и дважды непрерывно дифференцируема по своим переменным в области .

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

Представим уравнение (51) в конечно-разностной форме, заменяя и конечно-разностным аналогом в узловых точках :

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

, (52).

и дополнительным условиям:

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

(53)

Решая систему (53) с учетом дополнительных условий, получим - искомую функцию в точках .

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

,

а вторая производная остается прежней. Получим исходное уравнение в конечно-разностной форме:

.

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

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

.

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

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

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

(54)

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

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

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

7.2 Метод сеток для уравнений гиперболического типа

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

(55)

где , и будем искать решение уравнения (55) при заданных начальных и краевых условиях:

, , при (56)

при (57)

Решим эту задачу методом сеток. Как и в случае параболического уравнения, заменим прямоугольную область и сеточной , где , , . Шаг по оси - , шаг по оси - .

На сетке приближенно заменим дифференциальное уравнение (55) конечно-разностным аналогом:

 (58)

При уравнение (58) упрощается и принимает вид:

Откуда

(59)

Из уравнения (59) видно, что для получения значений в -м слое используются значения в двух предыдущих слоях -м и -м. Для начала вычислений по формуле (59) также необходимо знать значения и на нулевом слое . Используя начальное условие , можно определить значения на фиктивном слое с номером . Для этого заменим производную в условии конечно-разностным соотношением: , где . Отсюда находим . Зная значения на слое , можно начать вычисления. Краевые условия (59) используются для получения значений и .

8. Метод А.Н. Крылова для нахождения коэффициентов характеристического многочлена

Этот метод позволяет построить для заданной матрицы характеристический многочлен , который можно записать в виде:

Согласно теореме Гамильтона-Кэли сама матрица удовлетворяет характеристическому уравнению , а значит . Умножим это равенство на произвольный вектор и получим . Обозначив , , …, , будем иметь . Это векторное равенство эквивалентно системе уравнений относительно коэффициентов характеристического многочлена

,

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

Литература

Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989

Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Физматгиз, 1966

Калиткин Н.Н. Численные методы. М.: Наука, 1978

Марчук Г.И. Методы вычислительной математики. М.: Наука, 1989.

Моисеев В.С., Горбунов Д.А. Метод малого параметра для решения задач анализа и синтеза проектных решений на базе неявно заданных функциональных зависимостей. //Изв.вузов, Авиационная техника, 1998, 4, с.3-10

Иванов В.С., Ляшев А.С. Лабораторный практикум по дисциплине «Вычислительная техника в инженерных и экономических расчетах». Казань, КАИ, 1984.

Вахонина Г.С. Методическое руководство к выполнению лабораторных работ по дисциплине “Методы вычислений”. - Казань: КАИ, 1982.

Горбунов Д.А., Вахонина Г.С. Применение численных методов для решения инженерных задач на ЭВМ. Казань, Изд-во Казан. гос. техн. ун-та, 2001, 40с.

1. Размещено на www.allbest.ru