Каталог Рефератов - Методы компьютерных вычислений и их приложение к физическим задачам

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Методы компьютерных вычислений и их приложение к физическим задачам

b>Mathematica.

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

Maple.

Разработка компании Waterloo Maple Inc. Также очень популярный в научных кругах пакет аналитических преобразований и численных методов. Символический процессор Maple поставляется отдельно, в связи с чем производители других программных средств могут интегрировать его в свои разработки.

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

. То есть:

где - априорная погрешность метода на интервале интегрирования,

а r(x) - априорная погрешность метода на отдельном шаге интегрирования.

Обзор методов интегрирования.

Методы вычисления однократных интегралов называются квадратурными (для кратных интегралов - кубатурными).

1) Методы Ньютона-Котеса. Здесь ц(x) - полином различных степеней. Сюда относятся метод прямоугольников, трапеций, Симпсона.

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

3) Сплайновые методы. Здесь ц(x) - кусочный полином с условиями связи между отдельными полиномами посредством системы коэффициентов.

4) Методы наивысшей алгебраической точности. Обеспечивают оптимальную расстановку узлов сетки интегрирования и выбор весовых коэффициентов с(x) в задаче. Сюда относится метод Гаусса-Кристоффеля (вычисление несобственных интегралов) и метод Маркова.

Метод прямоугольников.

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

Выведем формулу метода прямоугольников из анализа разложения функции f(x) в ряд Тейлора вблизи некоторой точки x = xi.

…

Рассмотрим диапазон интегрирования от xi до xi + h, где h - шаг интегрирования.

Вычислим

…=

==.

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

В случае равного шага h на всем диапазоне интегрирования общая формула имеет вид

Здесь n - число разбиений интервала интегрирования,

Для справедливости существования этой оценки необходимо существование непрерывной f'(x).

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

то есть

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

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

Аппроксимация в этом методе осуществляется полиномом первой степени. Суть метода ясна из рисунка.

На единичном интервале.

В случае равномерной сетки (h = const)

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

Особенности поведения погрешности.

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

Однако рассмотрим график поведения апостериорной погрешности R результатов численного расчета в зависимости от числа n разбиений интервала (то есть при шаг ). На участке (1) погрешность уменьшается в связи с уменьшением шага h. Но на участке (2) начинает доминировать вычислительная погрешность, накапливающаяся в результате многочисленных арифметических действий. Таким образом, для каждого метода существует своя Rmin, которая зависит от многих факторов, но прежде всего от априорного значения погрешности метода R.

Уточняющая формула Ромберга.

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

Обозначим интеграл с числом разбиений n = 1 как

Уменьшив шаг в два раза, получим

Если последовательно уменьшать шаг в 2n раз, получим рекуррентное соотношение для расчета

Пусть мы вычислили четыре раза интеграл с n от 1 до 4. Представим следующий треугольник:

R(1;1)

R(2;1) R(2;2)

R(3;1) R(3;2) R(3;3)

R(4;1) R(4;2) R(4;3) R(4;4)

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

Правое нижнее значение в треугольнике - искомое уточненное значение интеграла.

Метод Симпсона.

Подинтегральная функция f(x) заменяется интерполяционным полиномом второй степени P(x) - параболой, проходящей через три узла, например, как показано на рисунке ((1) - функция, (2) - полином).

Рассмотрим два шага интегрирования (h = const = xi+1 - xi), то есть три узла x0, x1, x2, через которые проведем параболу, воспользовавшись уравнением Ньютона:

Пусть z = x - x0,

тогда

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

В итоге .

Для равномерной сетки и четного числа шагов n формула Симпсона принимает вид:

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

Блок-схема алгоритма метода Симпсона.

Методы Монте-Карло.

1) одномерная случайная величина - статистический вариант метода прямоугольников.

В качестве текущего узла xi берется случайное число, равномерно распределенное на интервале интегрирования [a, b].

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

Для R можно утверждать хотя бы ~.

2) двумерная случайная величина - оценка площадей.

Рассматриваются две равномерно распределенных случайных величины xi и yi, которые можно рассматривать как координаты точки в двумерном пространстве. За приближенное значение интеграла принимается количества точек S, попавших под кривую y = f(x), к общему числу испытаний N, т.е.

И первый, и второй случай легко обобщаются на кратные интегралы.

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

Мы записывали априорные оценки главного члена погрешности в виде R0 = Ahp, (1) где A - коэффициент, зависящий от метода интегрирования и вида подинтегральной функции; h - шаг интегрирования, p - порядок метода. Такого сорта оценку можно применить не только к методам интегрирования, но и ко многим другим численным алгоритмам.

Первая формула Рунге.

Пусть w - точное значение, к которому должен прийти численный метод (мы его не знаем). Результат численного расчета дает нам величину wh такую, что . (2)

Теперь вычислим ту же величину w с шагом kh, где константа k может быть как больше, так и меньше единицы. Коэффициент A будет одинаковый, так как вычисление осуществляется одним и тем же методом. Получаем . (3)

Приравняем правые части выражений (2) и (3) и пренебрежем бесконечно малыми величинами одинакового порядка малости.

Отсюда, учитывая (1), получим . (4) Эта формула, выражающая апостериорную оценку главного члена погрешности величины w путем двойного просчета с разным шагом, носит название первой формулы Рунге. При уменьшении шага главный член погрешности будет стремиться к полной погрешности R.

Вторая формула Рунге.

Так как модуль и знак апостериорной погрешности из формулы (4) известны, можно уточнить искомое значение . Это вторая формула Рунге. Однако теперь погрешность wcorr не определена, известно лишь, что она по модулю меньше R0.

Алгоритм Эйткена.

Способ оценки погрешности для случая, когда порядок метода p неизвестен. Более того, алгоритм позволяет опытным путем определить и порядок метода. Для этого в третий раз вычислим значение величины w с шагом k2h:

. (5)

Приравняем правые части выражений (5) и (3): . Отсюда:

. Подставим сюда значение R0 из (4):

Из этой формулы определяем знаменатель для (4). Кроме того, определяем порядок

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

6. Численное дифференцирование

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

Численное дифференцирование - некорректная задача, так как отсутствует устойчивость решения. При численном дифференцировании приходится вычитать друг из друга близкие значения функции. Это приводит к уничтожению первых значащих цифр, т.е. к потере части достоверных знаков числа. А так как значения функции обычно известны с определенной погрешностью, то все значащие цифры могут быть потеряны. На графике кривая (1) соответствует уменьшению погрешности дифференцирования при уменьшении шага; кривая (2) представляет собой неограниченно возрастающий (осциллирующий) вклад неустранимой погрешности исходных данных - значений функции y(x). Критерий выхода за оптимальный шаг при его уменьшении - «разболтка» решения: зависимость результатов вычислений становится нерегулярно зависящей от величины шага.

Пусть введена как интерполяционный многочлен Ньютона. В этом случае для произвольной неравномерной сетки:

, для i = 0,1…n-1, интерполяция полиномом первой степени.

, интерполяция полиномом второй степени.

В общем случае

Минимальное число узлов, необходимое для вычисления k-й производной, равно k + 1.

Оценка погрешности при численном дифференцировании может быть осуществлена по формуле

где n - число узлов функции, k - порядок производной.

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

, где h = x1 - x0 = const.

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

7. Численное решение систем линейных уравнений
Классы задач линейной алгебры

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

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

· вычисление определителей матриц ;

· нахождение обратных матриц ;

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

Постановка задачи решения СЛАУ: , (1) где - квадратная матрица коэффициентов размерности n, - вектор неизвестных, - вектор свободных коэффициентов. Иногда СЛАУ представляют в виде расширенной матрицы размерности n ? n+1, где в качестве последнего столбца фигурирует вектор свободных коэффициентов.

В координатном представлении такая СЛАУ выглядит следующим образом:

. (2)

Для решения СЛАУ применяют в основном два класса методов: прямые (выполняемые за заранее известное количество действий) и итерационные (обеспечивающие постепенную сходимость к корню уравнения, зависящую от многих факторов). Прямые методы обычно применяются для решения систем порядка n < 200, для бoльших n используются итерационные методы. Перед решением СЛАУ требуется проанализировать корректную постановку задачи:

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

Страницы: 1, 2, 3, 4, 5, 6

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.