|
|
| Методы компьютерных вычислений и их приложение к физическим задачам |
|
(3)Иными словами, если , число коэффициентов аппроксимации недостаточно для правильного воспроизведения графика экспериментальной зависимости. Если , многие коэффициенты в (2) не будут иметь физического смысла.Для решения задачи линейной аппроксимации в общем случае следует найти условия минимума суммы квадратов отклонений для (2). Задачу на поиск минимума можно свести к задаче поиска корня системы уравнений , k = 0…m. (4).Подстановка (2) в (1), а затем расчет (4) приведет в итоге к следующей системе линейных алгебраических уравнений: Далее следует решить полученную СЛАУ относительно коэффициентов c0…cm. Для решения СЛАУ обычно составляется расширенная матрица коэффициентов, которую называют матрицей Грама, элементами которой являются скалярные произведения базисных функций и столбец свободных коэффициентов:,где , , j = 0…m, k = 0…m.После того как с помощью, например, метода Гаусса найдены коэффициенты c0…cm, можно построить аппроксимирующую кривую или вычислить координаты заданной точки. Таким образом, задача аппроксимации решена.Аппроксимация каноническим полиномом.Выберем базисные функции в виде последовательности степеней аргумента x:ц0(x) = x0 = 1; ц1(x) = x1 = x; цm(x) = xm, m < n.Расширенная матрица Грама для степенного базиса будет выглядеть следующим образом: .Особенность вычислений такой матрицы (для уменьшения количества выполняемых действий) состоит в том, что необходимо сосчитать только элементы первой строки и двух последних столбцов: остальные элементы заполняются сдвигом предшествующей строки (за исключением двух последних столбцов) на одну позицию влево. В некоторых языках программирования, где отсутствует быстрая процедура возведения в степень, пригодится алгоритм расчета матрицы Грама, представленный далее.Выбор базисных функций в виде степеней x не является оптимальным с точки зрения достижения наименьшей погрешности. Это является следствием неортогональности выбранных базисных функций. Свойство ортогональности заключается в том, что для каждого типа полинома существует отрезок [x0, xn], на котором обращаются в нуль скалярные произведения полиномов разного порядка:, j ? k, с - некоторая весовая функция.Если бы базисные функции были ортогональны, то все недиагональные элементы матрицы Грама были бы близки к нулю, что увеличило бы точность вычислений, в противном случае при определитель матрицы Грама очень быстро стремится к нулю, т.е. система становится плохо обусловленной. Блок-схема алгоритма формирования матрицы Грама и аппроксимации полиномом. 1 Аппроксимация ортогональными классическими полиномами.Представленные ниже полиномы, относящиеся ко многочленам Якоби, обладают свойством ортогональности в изложенном выше смысле. То есть, для достижения высокой точности вычислений рекомендуется выбирать базисные функции для аппроксимации в виде этих полиномов.1) Полиномы Чебышева.Определены и ортогональны на [-1, 1] с весом . В интервал ортогональности всегда можно вписать область определения исходной функции с помощью линейных преобразований.Строятся следующим образом (рекуррентная формула):T0(x) = 1;T1(x) = x;Tk+1(x) = 2xTk(x) - Tk-1(x).2) Полиномы Лежандра.Определены и ортогональны на [-1, 1] с весом .Строятся следующим образом (рекуррентная формула):L0(x) = 1;L1(x) = x;.Сглаживание и линейная регрессия.Рассмотрим несколько наиболее простых с точки зрения программной реализации случаев аппроксимации (сглаживания).1) Линейная регрессия. В случае линейного варианта МНК (линейная регрессия) ц(x) = a + bx можно сразу получить значения коэффициентов a и b по следующим формулам:,,где , .2) Линейное сглаживание по трём точкам.3) Линейное сглаживание по пяти точкам.10. Решение нелинейных уравнений с одним неизвестным.Общие сведения о численном решении уравнений с одним неизвестным.Пусть задана непрерывная функция f(x). Требуется найти корни уравнения f(x) = 0 численными методами - это и является постановкой задачи. Численное решение уравнения распадается на несколько подзадач:1) Анализ количества, характера и расположения корней (обычно путем построения графика функции или исходя из физического смысла исследуемой модели). Здесь возможны следующие варианты:· единственный корень;· бесконечное множество решений;· корней нет;· имеется несколько решений, как действительных, так и мнимых (например, для полинома степени n). Корни четной кратности выявить сложно.2) Локализация корней (разбиение на интервалы) и выбор начального приближения к каждому корню. В простейшем случае можно протабулировать функцию с заданным шагом. Если в двух соседних узлах функция будет иметь разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере один).3) Вычисление каждого (или интересующего нас) корня уравнения с требуемой точностью. Уточнение происходит с помощью методов, изложенных ниже.Метод дихотомии (бисекций).Иначе называется методом половинного деления. Пусть задан начальный интервал [x0, x1], на котором f(x0)f(x1) ? 0 (т.е. внутри имеется не менее чем один корень). Найдем x2 = ? (x0 + x1) и вычислим f(x2). Если f(x0)f(x2) ? 0, используем для дальнейшего деления отрезок [x0, x2], если > 0 - используем для дальнейшего деления отрезок [x1, x2], и продолжаем деление пополам.Итерации продолжаются, пока длина отрезка не станет меньше 2о - заданной точности. Тогда середина последнего отрезка даст значение корня с требуемой точностью. В качестве иного критерия можно взять | f(x)| ? оy.Скорость сходимости метода невелика, однако он прост и надежен. Метод неприменим к корням четной кратности. Если на отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс.Если на заданном интервале предполагается несколько корней, то существует возможность последовательно исключать найденные корни из рассмотрения. Для этого воспользуемся вспомогательной функцией , где - только что найденный корень. Для функций f(x) и g(x) совпадают все корни, за исключением (в этой точке полюс функции g(x)). Для достижения требуемой точности рекомендуется грубо приблизиться к корню по функции g(x), а затем уточнить его, используя f(x).Метод хорд.Идея метода проиллюстрирована рисунком. Задается интервал [x0, x1], на котором f(x0)f(x1) ? 0, между точками x0 и x1 строится хорда, стягивающая f(x). Очередное приближение берется в точке x2, где хорда пересекает ось абсцисс. В качестве нового интервала для продолжения итерационного процесса выбирается тот, на концах которого функция имеет разные знаки. Условия выхода из итерационного цикла: или | f(x)| ? оy.Для вывода итерационной формулы процесса найдем точку пересечения хорды (описываемой уравнением прямой) с осью абсцисс: ax2 + b = 0, где ; b = f(x0) - ax0. Отсюда легко выразить .Метод хорд в большинстве случаев работает быстрее, чем метод дихотомии. Недостатки метода те же, что и в предыдущем случае.Метод Ньютона (касательных).Пусть x0 - начальное приближение к корню, а f(x) имеет непрерывную производную. Следующее приближение к корню найдем в точке x1, где касательная к функции f(x), проведенная из точки (x0, f0), пересекает ось абсцисс. Затем точно так же обрабатываем точку (x1, f1), организуя итерационный процесс. Выход из итерационного процесса по условию .Уравнение касательной, проведенной из точки (x0, f0): y(x) = f /(x0)(x-x0) + f(x0) дает для y(x1) = 0 следующее выражение:, (1)которое и используется для организации итерационного процесса. Итерации сходятся, только если всюду выполняется условие ; в противном случае сходимость будет не при любом начальном приближении, а только в некоторой окрестности корня. Итерации будут сходиться к корню с той стороны, с которой . Метод обладает самой высокой скоростью сходимости: погрешность очередного приближения примерно равна квадрату погрешности предыдущего приближения. Метод можно использовать для уточнения корней в области комплексных чисел, что необходимо при решении многих прикладных задач, например при численном моделировании электромагнитных колебательных и волновых процессов с учетом временной и пространственной диссипации энергии.Недостатком метода можно указать необходимость знать явный вид первой и второй производных, так как их численный расчет приведет к уменьшению скорости сходимости метода. Иногда, ради упрощения расчетов, используют т.н. модифицированный метод Ньютона, в котором значение f /(x) вычисляется только в точке x0, при этом число итераций увеличивается, но расчеты на каждой итерации упрощаются.Метод секущих.В отличие от метода Ньютона, можно заменить производную первой разделенной разностью, найденной по двум последним итерациям, т.е. заменить касательную секущей. При этом первый шаг итерационного процесса запишется так:.Для начала итерационного процесса необходимо задать x0 и x1, которые не обязательно ограничивают интервал, на котором функция должна менять знак; это могут быть любые две точки на кривой. Выход из итерационного процесса по условию .Сходимость может быть немонотонной даже вблизи корня. При этом вблизи корня может происходить потеря точности, т.н. «разболтка решения», особенно значительная в случае кратных корней. От разболтки страхуются приемом Гарвика: выбирают некоторое оx и ведут итерации до выполнения условия . Затем продолжают расчет, пока убывает. Первое же возрастание может свидетельствовать о начале разболтки, а значит, расчет следует прекратить, а последнюю итерацию не использовать.Метод простых итераций.Суть метода простых итераций в принципе совпадает с методом, изложенным для решения систем линейных алгебраических уравнений. Для нелинейного уравнения метод основан на переходе от уравнения f(x) = 0 (2)к эквивалентному уравнению x = ц (x). Этот переход можно осуществить разными способами, в зависимости от вида f(x). Например, можно положить ц (x) = x + bf(x), (3)где b = const, при этом корни исходного уравнения (2) не изменятся.Если известно начальное приближение к корню x0, то новое приближение x1 = ц (x0), т.е. общая схема итерационного процесса: xk+1 = ц (xk). (4)Наиболее простой критерий окончания процесса .Критерий сходимости метода простых итераций: если вблизи корня |ц/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого x, то итерации сходятся при любом начальном приближении. Исследуем выбор константы b в функции (3) с точки зрения обеспечения максимальной скорости сходимости. В соответствии с критерием сходимости наибольшая скорость сходимости обеспечивается при |ц/(x)| = 0. При этом, исходя из (3),b = -1/f /(x), и итерационная формула (4) переходит в ,т.е. в формулу метода Ньютона (1). Таким образом, метод Ньютона является частным случаем метода простых итераций, обеспечивающим самую высокую скорость сходимости из всех возможных вариантов выбора функции ц (x).11. Численное решение систем нелинейных уравненийПостановка задачиТребуется решить систему нелинейных уравнений (1). В координатном виде эту задачу можно записать так: , где 1 ? k ? n.Убедиться в существовании решения и количестве корней, а также выбрать нулевое приближение в случае системы двух уравнений с двумя неизвестными можно, построив графики функций в удобных координатах. В случае сложных функций можно посмотреть поведение аппроксимирующих их полиномов. Для трех и более неизвестных, а также для комплексных корней, удовлетворительных способов подбора начального приближения нет.Метод Ньютона.Обозначим некоторое приближение к корню системы уравнений . Пусть малое . Вблизи каждое уравнение системы можно линеаризовать следующим образом:, 1 ? k ? n. (2)Это можно интерпретировать как первые два члена разложения функции в ряд Тейлора вблизи . В соответствии с (1), приравнивая (2) к нулю, получим:, 1 ? k ? n. (3)Мы получили систему линейных уравнений, неизвестными в которой выступают величины . Решив ее, например, методом Гаусса, мы получим некое новое приближение к , т.е. . Выражение (3) можно представить как обобщение на систему уравнений итерационного метода Ньютона, рассмотренного в предыдущей главе:, (4)где в данном случае
Страницы: 1, 2, 3, 4, 5, 6
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
