Вариант 9. Методы решения алгебраических и трансцендентных уравнений. Приближённое решение уравнения методом Ньютона

  • ID: 23147 
  • 18 страниц
320 рубСкачать

как получить скидку

Var09.docx

задание 1.mcd

задание 2.mcd

Задание 3.mcd

задание 4.mcd

задание 5.mcd

задание 6.mcd

задание 7.mcd

задание 8.mcd

Содержание:


Вариант 9. Методы решения алгебраических и трансцендентных уравнен…

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

Приближённое решение уравнения методом Ньютона.

Если известно хорошее начальное приближение решения уравнения f(x) = 0, то эффективным методом повышения точности является метод Ньютона (метод касательных). Метод состоит в построении итерационной последовательности xn+1 = xn – f(xn)/f(xn), сходящейся к корню уравнения f(x) = 0. Сформулируем достаточные условия сходимости метода.

Теорема. Пусть f(x) определена и дважды дифференцируема на [a,b], причём f(a)f(b)<0, а производные f(x), f(x) сохраняют знак на отрезке [a,b]. Тогда, исходя из начального приближения x0[a,b], удовлетворяющего неравенству f(x0)f(x0)>0, можно построить последовательность

n = 0,1,2,…

сходящуюся к единственному на [a,b] решению  уравнения f(x) = 0.

Метод Ньютона допускает простую геометрическую интерпретацию. Если через точку с координатами (xn;f(xn)) (рис. 1.2) провести касательную, то абсцисса точки пересечения этой касательной с осью Ox и есть очередное приближение xn+1 корня уравнения f(x) = 0.

Для оценки погрешности n-го приближения корня можно воспользоваться неравенством

где M2 – наибольшее значение модуля второй производной |f(x)| на отрезке [a,b]; m1 –наименьшее значение модуля первой производной |f(x)| на отрезке [a,b]. Таким образом, если |xn – xn-1|<, то | - xn|M22/(2m1). Последнее соотношение означает, что при хорошем начальном приближении корня после каждой итерации число верных десятичных знаков в очередном приближении удваивается, т.е. процесс сходится очень быстро. Значит, если необходимо найти корень с точностью , то итерационный процесс можно прекратить, когда

Опишем один шаг итераций. Если на (n – 1)-м шаге очередное приближение xn-1 не удовлетворяет условию окончания процесса, то вычисляем величины f(xn-1), f(xn-1) и следующее приближение корня xn = xn-1 – f(xn-1)/f(xn-1). При выполнении условия

величину xn принимаем за приближённое значение корня , вычисленное с точностью .

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

Задание

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

Вариант 09

Решение задач в пакете MathCAD находятся в приложении к работе.

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

Δ2 – алгоритм Эйткена

Шаг 0. Ввод x0 (начального приближения), φ(x) (исходной функции), q (оценки модуля производной), ε (допустимой абсолютной погрешности).

Шаг 1. Вычисление значений.

Шаг 2. Δ2 – ускорение:.

Шаг 3. Вычисление контрольного значения:.

Шаг 4. Проверка на точность: если, то положить, вычислить и вернуться к шагу 2.

Шаг 5. Положить (с точностью до ε).

Применяя метод Эйткена, не следует забывать о проблеме своевременного прерывания счёта из-за потерь точности при вычитании близких чисел. Подключение Δ2 – ускорения на ранней стадии МПИ, когда x0 далеко от ξ, может привести к расходимости процесса, по крайней мере, в случае, когда.

Задание

Вариант 09

Функция:

Выполненное задание в при помощи системы MathCAD представлено в приложении.

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

Метод наискорейшего спуска

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

Из функций f и g системы образуем новую функцию

Так как эта функция неотрицательна, то найдётся точка (и не единственная) такая, что

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

Последовательность точек - приближёний к точке минимума - обычно получают по рекуррентной формуле

где - вектор, определяющий направление минимизации, а - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функции двух переменных - «спуск на дно» поверхности z =, итерационный метод можно назвать методом спуска, если вектор при каждом k является направлением спуска (т.е. существует такое α > 0, что ) и если множитель подбирается так, чтобы выполнялось условие релаксации, означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

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

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

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

Оптимальный шаг в направлении антиградиента – это такой шаг, при котором значение - наименьшее среди всех других значений в этом фиксированном направлении, т.е. когда точка является точкой условного минимума. Следовательно, можно рассчитывать на наиболее быструю сходимость метода (2.24), если полагать в нём

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

Задание

Найти решение системы.

Задача решается только в пакете MathCAD.

Вариант 09. Система уравнений:

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

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

Аппроксимация кубическим сплайном

Для простоты рассмотрим проблему аппроксимации с помощью кубического сплайна.

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

Пусть имеется некоторая кривая f(x), а для неё известен набор опорных точек xi, yi (i=0..n), где n - количество интервалов между ними. На каждом интервале исходная функция аппроксимируется кубическим полиномом (сплайном)

(4.1)

Для n интервалов необходимо найти 4*n неизвестных, поскольку для каждого интерполирующего сплайна Sj вычисляются значения коэффициентов ai, bi, ci, di.

Любой сплайн должен удовлетворять четырем условиям:

1. В каждой нижней границе интервала сплайн проходит через опорную точку.

(4.2)

2. В каждой верхней границе интервала сплайн проходит через опорную точку.

(4.3)

Ширина интервала

3. Для каждой нижней граничной точки интервала сплайн имеет одинаковую крутизну в обоих граничащих интервалах.

(4.4)

4. Для каждой верхней граничной точки интервала сплайн имеет одинаковую крутизну в обоих граничащих интервалах.

(4.5)

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

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

б) крутизна любого интерполирующего сплайна в обеих граничных точках фиксирована.

Вывод коэффициентов.

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

Подставляя в (4.2) x = xi, получаем

di = yi, i = 0,1,…,n-1 (4.10)

Из второго условия подставляем уравнение (4.3) и x = xi + hi в (4.1) с учётом (4.10) получаем

Согласно третьему условию:

Подставляя в выражение (5.12) уравнение (5.4) имеем:

Для удовлетворения четвёртого условия вычислим вторую производную интерполирующего сплайна:

Подставляя в это выражение уравнение (4.5), получаем:

Посредством исключения коэффициентов а и с из уравнений (4.13), (4.11) и (4.15) вместе с граничными условиями (4.6), (4.7) или (4.8), (4.9) получаем систему линейных уравнений для всех b. Теперь решим (4.15) относительно

Подставив (4.16) в (4.11):

Это уравнение в свою очередь решим относительно

Для первого члена в правой части (4.18) в дальнейшем будем пользоваться сокращением

Опорные точки должны быть сопоставимы с непрерывной функцией, т.е. функция не должна иметь скачков, поскольку из-за hi=0 значение ei стремилось бы к бесконечности.

Чтобы исключить коэффициенты ai, ci подставим в уравнения (4.16) и (4.18) в уравнение (4.13) и после преобразования запишем:

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

Граничное условие А.

Подставляя уравнение (4.9) при i = 0 и x = xi в уравнение (4.14), получаем

b1 = 0 (4.21)

Для упрощённого расчёта граничного условия (4.7) допустим, что за опорной точкой xn существует другой интерполирующий сплайн, для которого условия (4.2), (4.4) и (4.5) выполняются. Согласно последнему условию

Подставляя это выражение при i = n и x = xn в уравнение (4.14) получаем

bn = 0 (4.22)

Аналогичным образом можно записать (4.20) и для i = n-1, т.е.:

Уравнения (4.16) и (4.19) представляют собой систему линейных уравнений, с помощью которой вычисляется n-1 сплайн-коэффициентов b1...bn-1. В матрице коэффициентов заполненными оказываются только главная диагональ и две соседние диагонали, а все остальные элементы равны 0. Такая система уравнений называется трёхдиагональной.

После решения системы уравнений, приведённой выше, предполагается, что все коэффициенты bi известны. С помощью уравнения (4.16) вычисляются все n ai, а с помощью (4.18) - все коэффициенты ci.

Граничное условие Б.

С учётом граничных условий (4.8) и (4.9) создаётся система из n уравнений для коэффициентов bi. Подставляя (4.8) для i = 1 и x = x1 получаем

c1 = ma (4.25)

Из уравнения (4.18)

Таким образом, получаем систему уравнений

которую необходимо решить относительно bn-1 и bn-2

Уравнения (4.20), (4.26) и (4.32) образуют систему линейных уравнений всех сплайн-коэффициентов b1...bn-1. Сиcтема трёхдиагональна, однако её матрица коэффициентов в отличии от уравнения (4.24) не симметрична. После решения этой системы по уравнениям (4.28) и (4.16) рассчитаем коэффициенты ai, а по уравнению (4.13) коэффициенты ci.

Моделирование сплайн-интерполяции.

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

Функция Spline реализует алгоритм вычисления сплайн-коэффициентов с учётом граничного условия А. Результатом вычисления является матрица размерностью n*4 в строках которой записаны коэффициенты a, b, c, d для каждой из n сплайн функции. Входные параметры - векторы x, y - исходные опорные точки.

Функция Function(x) вычисляет для заданного x значения сплайна.

Задание

Вычислить значения заданной функции f(x) в узлах интерполяции xi = a + h(i – 1), i = 1, 2,…, N, на отрезке [a,b]. По вычисленной таблице построить интерполяционный кубический сплайн S(x). Сравнить вычисленные значения с точными значениями функции в точках xj. Построить график f(x) и S(x).

Исходные данные:

Вариант 09

Функция:

Промежуток:

Число узлов:

Решение данного задания приведено в приложении.

Тригонометрическая интерполяция

Пусть функция f(х) задана на отрезке [0,2] таблицей значении f(xi) в равноотстоящих узлах (i=1, 2..., 2N+1). Тригонометрическим многочленом степени М называют многочлен.

Задача тригонометрической интерполяции состоит в построении тригонометрического интерполяционного многочлена наименьшей степени, удовлетворяющего условиям Pм(xi)=f(xi), i = l,…, 2N+1. Можно показать, что решением этой задачи является тригонометрический многочлен

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

Широкие возможности тригонометрической интерполяции следуют из того факта, что с возрастанием N многочлен Р(х) аппроксимирует f(x) с возрастающей точностью, т. е.

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

Задание

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

С помощью полученного полинома вычислить значение функции и в точках (i=1, 2..., 2N+1) (это уже предусмотрено в функции).

Исходные данные

Вариант 09

Точки:

-1.32; -1.28; -1.26; -1.24; 1.25; -1.25; -1.25; -1.26; -1.27; -1.29; -1.29; -1.33; -1.34; -1.37; -1.37; -1.37; -1.37; -1.36; -1.36; -1.35; -1.34

Промежуток:

Решение данного задания приведено в приложении.

Методы численного интегрирования

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

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

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

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

Площадь трапеции на каждом отрезке:

Погрешность аппроксимации на каждом отрезке:, где

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

Погрешность формулы трапеций:, где

Задание

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

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

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

Идея всех методов численного дифференцирования функций сводится к замене исходной функции f(x) некоторой функцией P(x), её интерполирующей (чаще всего полиномом или сплайном). Затем полагают:

При

Если для интерполирующей функции известна погрешность R(x) = f(x) – P(x), то погрешность вычисления производной функции f(x) может быть вычислена по формуле

Следует отметить, что численное дифференцирование представляет собой операцию менее точную, чем интегрирование. Близость друг к другу ординат двух кривых y = f(x) y = P(x) на [a,b] еще не гарантирует близость на этом отрезке их производных, т.е. малого расхождения угловых коэффициентов касательных к графикам рассматриваемых кривых (рис.5.7).

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

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

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

Введем переменную

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

Или

Учитывая

Вторая производная:

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

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

Оценка погрешности вычисления производных функции

Задание

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

Решение задания представлено в приложении.

Приближенное решение задачи Коши

Метод Эйлера

Пусть требуется найти приближенное решение дифференциального уравнения y'=f(x,у), удовлетворяющее начальному условию у(х0)=у0. Численное решение задачи состоит в построении таблицы приближенных значений у1, у2,…,yn решения уравнения у(х) в точках x1, x2..., xn. Чаще всего хi = x0+ih, i=1, 2..., п. Точки xi называются узлами сетки, а величина h—шагом (h>0).

В методе Эйлера величины уi вычисляются по формуле

Этот метод относится к группе одношаговых методов, в которых для расчета точки (xi+1;.yi+1) требуется информация только о последней вычисленной точке (xi; yi). Метод допускает простую геометрическую интерпретацию. Предположим, что известна точка (хi; yi) на искомой интегральной кривой. Тогда касательная к этой кривой, проходящая через точку (хi; yi), определяется уравнением y=y'i(x - xi)+yi, а так как y'i =f(хi, yi) и xi+1=xi+h, то yi+1=yi+hf(xi, yi). Для оценки погрешности метода на одном шаге сетки разложим точное решение в ряд Тейлора в окрестности узла хi

(2.63)

Если расчетные формулы численного метода согласуются с разложением в ряд Тейлора до членов порядка hp, то число р называют порядком метода. Таким образом, метод Эйлера—метод первого порядка.

Для практической оценки погрешности расчета можно рекомендовать правило Рунге. Для этого проведем вычисления с шагом h и h/2 и сравним величины уi(h) и уi(h/2). За оценку погрешности вычислений с шагом h/2 можно принять величину

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

удовлетворяющее начальным условиям y1(x0)= y10, y2(x0)= y20,…, yn(x0)= yn0. Или в векторной форме:

Y(x)={y1(x), y2(х)...,yn(x)}, Y0={y10, y20,…, yn0}. Приближенные значения уki точного решения yk(хi) в точках xi вычисляются по формулам

Задание

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

Вариант 09

Решение задания представлено в приложении.