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

Реферат по курсу:

«Основы информационных технологий»

Тема № 7

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

Содержание

Содержание

1. Введение

1.1. Задачи для обыкновенных дифференциальных уравнений

1.2. Квадратурные формулы

2. Метод сеток

2.1 Теоретические основы метода сеток для решения задачи Коши

2.3 Погрешность аппроксимации

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

2.4 Основная теорема метода сеток

3. Виды конечно-разностных схем

3.1 Явная схема 1-го порядка (Эйлера)

3.2 Неявная схема 1-го порядка

3.3 Неявная схема 2-го порядка

3.4 Схема предиктор-корректор (Рунге-Кутта) 2-го порядка

3.5 Многошаговые схемы Адамса

Список литературы

1. Введение

1.1 Задачи для обыкновенных дифференциальных уравнений

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

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

(1)

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

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

краевая (граничная) задача, когда часть условий задается на границе a (при x = a), остальные условия - на границе b (при x = b). Обычно это значения искомых функций и их производных на границах;

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

. (2)

При изложении методов решения задачи Коши воспользуемся компактной записью задачи (1), (2) в векторной форме.

. (3)

Требуется найти для a x b.

1.2 Квадратурные формулы

Формулы для вычисления интеграла получают следующим образом. Область интегрирования [a, b] разбивают на малые отрезки , в общем случае разной длины. Значение интеграла по всей области равно сумме интегралов на отрезках . Выбирают на каждом отрезке [xi, xi+1] 1-5 узлов и строят для каждого отрезка интерполяционный многочлен соответствующего порядка. Вычисляют интеграл от этого многочлена на отрезке. В результате получают выражение интеграла (формулу численного интегрирования) через значения подынтегральной функции в выбранной системе точек. Такие выражения называют квадратурными формулами.

2. Метод сеток

2.1 Теоретические основы метода сеток для решения задачи Коши

дифференциальный уравнение формула схема

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

Таким образом, процедура численного решения задач ЕК состоит из трех основных этапов.

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

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

3) Заключительный этап -- программная реализация этого алгоритма на ЭВМ.

Суть метода сеток

1) в области интегрирования выбирается упорядоченная система точек называемая сеткой. Точки называют узлами, а - шагом сетки. Если , сетка называется равномерной. Для упрощения в дальнейшем будим считать сетку равномерной;

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

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

Согласно этому способу для получения конечно-разностной схемы проинтегрируем уравнение (3) на каждом интервале для k=0, ..., n-1 и разделим на длину этого интервала:

. (4)

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

. (5)

Здесь xj - точки внутри интервала, используемые для получения квадратурной формулы (см. подразд. 4.3).

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

2.3 Погрешность аппроксимации

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

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

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

.

Воспользовавшись соотношением (4), получаем простое выражение для вычисления :

, (6)

которая зависит от шага сетки.

Говорят, что разностная схема (5) аппроксимирует исходную дифференциальную задачу с порядком p, если при . Из (6) следует, что порядок аппроксимации на 1 меньше, чем порядок погрешности используемой квадратурной формулы на интервале [xk, xk+1].

Чем больший порядок аппроксимации p , тем выше точность решения:

.

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

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

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

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

2.4 Основная теорема метода сеток

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

, (7)

где С0 - константа устойчивости.

Неустойчивость обычно проявляется в том, что с уменьшением h решение при возрастании k, что легко устанавливается экспериментально с помощью просчета на последовательности сеток с уменьшающимся шагом h, h/2, h/4… Если при этом , то метод неустойчив. Таким образом, если имеется аппроксимация и схема устойчива, то, выбрав достаточно малый шаг h, можно получить решение с заданной точностью. При этом затраты на вычисления резко уменьшаются с увеличением порядка аппроксимации p, т.е. при большем p можно достичь той же точности, используя более крупный шаг h.

3. Виды конечно-разностных схем

Большое разнообразие методов обусловлено возможностью по-разному выбирать узлы и квадратурные формулы для аппроксимации интеграла в (4) при получении схемы (5).

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

• 1. Явная схема 1-го порядка (Эйлера)
• 2. Неявная схема 1-го порядка
• 3. Неявная схема 2-го порядка
• 4. Схема предиктор-корректор (Рунге-Кутта) 2-го порядка

5. Многошаговые схемы Адамса

3.1 Явная схема 1-го порядка (Эйлера)

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

3.2 Неявная схема 1-го порядка

Эффективность неявной схемы заключается в том, что у нее константа устойчивости С0 значительно меньше, чем у явной схемы.

3.3 Неявная схема 2-го порядка

Так как формула трапеций имеет третий порядок точности на интервале , то погрешность аппроксимации (h) - второй.

3.4 Схема предиктор-корректор (Рунге-Кутта) 2-го порядка

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

3.5 Многошаговые схемы Адамса

При построении всех предыдущих схем для вычисления интеграла в правой части (4) использовались лишь точки в диапазоне одного шага . Поэтому при реализации таких схем для вычисления следующего значения требуется знать только одно предыдущее значение , т.е. рекуррентная последовательность получается первого порядка. Такие схемы называют одношаговыми. Мы, однако, видели, что для повышения точности при переходе от xk к xk+1 приходилось использовать и значения функции F внутри интервала . Схемы, в которых это используется (M4,M5,...), называют схемами с дробными шагами. В этих схемах повышение точности достигается за счет дополнительных затрат на вычисление функции F(x) в промежуточных точках интервала .

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

Список литературы

1. Синицын А.К., Навроцкий А.А. Алгоритмы вычислительной математики : учебно-метод. пособие по курсу «Основы алгоритмизации и программирования» - Мн.: БГУИР, 2007. - 80 с.

2. Синицын А. К. Практикум по курсу «Алгоритмы вычислительной математики»: учеб. пособие для студ. 1-2 го курсов всех спец. - Мн. : БГУИР, 1996.

3. Синицын А. К., Навроцкий, А. А. Алгоритмы вычислительной математики : лаб. практикум по курсу «Программирование» для студ. 1-2 го курсов всех спец. - Мн. : БГУИР, 2002.

4. Самарский А.А. Теория разностных схем. - М.: Наука, 1983

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

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

7. Берковский Б. М., Полевиков В. К. Вычислительный эксперимент в конвекции. -- Мн: Изд-во «Университетское», 1988.

Размещено на Allbest.ru