This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
courses:computational_mathematics:prac3 [2021/07/08 20:12] andrey.suchkov [Таблицы] |
courses:computational_mathematics:prac3 [2022/07/04 05:40] andrey.suchkov removed |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Практическая работа №3: Решение нелинейных уравнений и систем ====== | + | ====== Практическая работа №3: Численное дифференцирование ====== |
===== Цель работы ===== | ===== Цель работы ===== | ||
- | Сформировать представление о методах решения нелинейных уравнений и систем нелинейных уравнений, выработать умение составлять и применять алгоритмы для решения уравнений и систем уравнений, привить навык использования программных средств для решения нелинейных уравнений и систем нелинейных уравнений. | + | Проверить правильность порядка точности и определить наивысшую достижимую точность (наименьшую погрешность) в стандартном режиме вычислений с плавающей точкой (8-байтовые числа, типа double) для пяти разностных формул численного дифференцирования. |
- | + | ||
- | ===== Основные теоретические положения ===== | + | |
- | ==== Решение нелинейных уравнений ==== | + | |
- | Численное решение нелинейных (алгебраических или трансцендентных) уравнений вида \[ f(x) = 0\] заключается в нахождении значений $ x $, удовлетворяющих (с заданной точностью) данному уравнению и состоит из следующих основных этапов: | + | |
- | - //Отделение// (изоляция, локализация) корней уравнения. | + | |
- | - //Уточнение// с помощью некоторого вычислительного алгоритма конкретного выделенного корня с заданной точностью. | + | |
- | Целью первого этапа является нахождение отрезков из области определения функции $ f(x) $, внутри которых содержится только один корень решаемого уравнения. Иногда ограничиваются рассмотрением лишь какой-нибудь части области определения, вызывающей по тем или иным соображениям интерес. Для реализации данного этапа используются //графические// или //аналитические// способы. | + | |
- | + | ||
- | При аналитическом способе отделения корней полезна следующая теорема. | + | |
- | + | ||
- | **Теорема.** //Непрерывная строго монотонная функция $ f(x) $ имеет и притом единственный нуль на отрезке $ [a, b] $ тогда и только тогда, когда на его концах она принимает значения разных знаков.// | + | |
- | + | ||
- | Достаточным признаком монотонности функции $ f(x) $ на отрезке $ [a, b] $ является сохранение знака производной функции. | + | |
- | + | ||
- | Графический способ отделения корней целесообразно использовать в том случае, когда имеется возможность построения графика функции $ y = f(x) $. Наличие графика исходной функции дает непосредственное представление о количестве и расположении нулей функции, что позволяет определить промежутки, внутри которых содержится только один корень. Если построение графика функции $ y = f(x) $ вызывает затруднение, часто оказывается удобным преобразовать уравнение $ f(x) = 0 $ к эквивалентному виду $ f_1(x) = f_2(x) $ и построить графики функций $ y = f_1(x) $ и $ y = f_2(x) $. Абсциссы точек пересечения этих графиков будут соответствовать значениям корней решаемого уравнения. | + | |
- | + | ||
- | Так или иначе, при завершении первого этапа, должны быть определены промежутки, на каждом из которых содержится только один корень уравнения. | + | |
- | + | ||
- | Для уточнения корня с требуемой точностью применяются различные итерационные методы, заключающийеся в построении числовой последовательности $ x^{(k)} $ ($ k = 0, 1, 2, \dots $), сходящейся к искомому корню $ x^{(*)} $ уравнения $ f(x) = 0$. | + | |
- | + | ||
- | ==== Решение систем нелинейных уравнений ==== | + | |
- | Систему нелинейных уравнений с n неизвестными можно записать в виде | + | |
- | \[ | + | |
- | \left\{ | + | |
- | \begin{aligned} | + | |
- | &f_1(x_1, x_2, \dots, x_n) = 0 \\ | + | |
- | &f_2(x_1, x_2, \dots, x_n) = 0 \\ | + | |
- | &\dots\dots\dots\dots\dots\dots\dots \\ | + | |
- | &f_n(x_1, x_2, \dots, x_n) = 0 \\ | + | |
- | \end{aligned} | + | |
- | \right. | + | |
- | \] | + | |
- | или, более коротко, в векторной форме \[ F(X) = 0, \] где $ X = (x_1, x_2, \dots, x_n)^T $ -- вектор неизвестных, $ F = (f_1, f_2, \dots, f_n)^T $ -- вектор-функция. | + | |
- | + | ||
- | В редких случаях для решения такой системы удается применить метод последовательного исключения неизвестных и свести решение исходной задачи к решению одного нелинейного уравнения с одним неизвестным. Значения других неизвестных величин находятся соответствующей подстановкой в конкретные выражения. Однако в подавляющем большинстве случаев для решения систем нелинейных уравнений используются итерационные методы. | + | |
- | + | ||
- | В дальнейшем предполагается, что ищется изолированное решение нелинейной системы. | + | |
- | + | ||
- | Как и в случае одного нелинейного уравнения, локализация решения может осуществляться на основе специфической информации по конкретной решаемой задаче (например, по физическим соображениям), и -- с помощью методов математического анализа. При решении системы двух уравнений, достаточно часто удобным является графический способ, когда месторасположение корней определяется как точки пересечения кривых $ f_1(x_1, x_2) = 0 $, $ f_2(x_1, x_2) = 0 $ на плоскости $ (x_1, x_2) $. | + | |
===== Постановка задачи ===== | ===== Постановка задачи ===== | ||
- | Численно решить уравнение и систему уравнений методами Ньютона и простых итераций с заданной точностью $ \varepsilon $. Значение $ \varepsilon $ варьируется от 0.1 до 0.000001. | + | Сравнить точные значения $ f'(x_0) $, $ f''(x_0) $ с конечноразностными первыми производными 1-го, 2-го и 4-го порядков точности и конечноразностными вторыми производными 2-го и 4-го порядков точности, вычисляемыми по последовательно уменьшающимися вдвое значениям шага, если $ f(x) = \cfrac A{x^2 + px + q} $, $ x_0 = a $. Значения $ a $, $ A $, $ p $, $ q $ берутся из п/р №2. |
===== Порядок выполнения работы ===== | ===== Порядок выполнения работы ===== | ||
- | - При решении уравнения $ f(x) = 0 $: | + | - Реализовать функции для вычисления точных значений $ f(x) $, $ f'(x) $, $ f''(x) $. |
- | - Графически или аналитически отделить корни уравнения $ f(x) = 0 $, т.е. найти отрезки $ [a, b] $, на которых функция удовлетворяет условиям теоремы Больцано-Коши. | + | - Реализовать функции для вычисления приближённых формул $ f'(x) $ 1-го, 2-го и 4-го порядка точности, а также $ f''(x) $ 2-го и 4-го порядка точности. |
- | - Составить подпрограмму вычисления функции $ f(x) $. | + | - Вычислить точные значения производных с точностью до 15-ти знаков после запятой. |
- | - Для метода Ньютона: | + | - Посчитать погрешности (разности между точными значениями соответствующей производной и полученными по каждой из пяти разностных формул) при последовательных уменьшениях шага в два раза. |
- | - Составить программу ''newton()'' для вычисления корня уравнения методом Ньютона с заданной точностью $ \varepsilon $. | + | - Результаты для каждой формулы вывести в виде таблицы. Таблица должна состоять из трёх колонок: номер шага, сам шаг и величина погрешности. |
- | - Провести вычисления по программе для каждого корня. Заполнить табл. 1 при различных значениях $ \varepsilon $. Сделать выводы. | + | - Построить график зависимости погрешности от шага для каждой формулы. Для удобства график лучше выводить в двойном логарифмическом масштабе. |
- | - Для наименьшего корня (**для нечётных вариантов**) и для наибольшего корня (**для чётных вариантов**) заполнить табл. 2 при $ \varepsilon = 0.000001 $. Сделать выводы. | + | - Ориентируясь по графику и таблице для каждой формулы указать наивысшую достижимую точность (наименьшую погрешность) и номер шага (не сам шаг!), на котором эта погрешность была достигнута. |
- | - Теоретически и экспериментально исследовать скорость сходимости и обусловленность метода. Сделать выводы | + | - Сделать выводы. |
- | - Для метода простых итераций: | + | |
- | - Привести уравнение $ f(x) = 0 $ к виду $ x = \varphi(x) $ и проверить функцию $ \varphi(x) $ на сходимость. Если сходимость не выполняется при любом преобразовании уравнения $ f(x) = 0 $ (необходимо это показать!), то привести функцию $ \varphi(x) $ к виду $ \varphi(x) = x + \lambda f(x) $, где $ \lambda $ -- некоторая константа. Составить программу ''phi()'' для функции $ \varphi(x) $, удовлетворяющей сходимости. | + | |
- | - Составить программу ''siter()'' для вычисления корня уравнения методом простых итераций с заданной точностью $ \varepsilon $. | + | |
- | - Провести вычисления по программе для каждого корня. Заполнить табл. 1 при различных значениях $ \varepsilon $. Сделать выводы. | + | |
- | - Для наименьшего корня (**для нечётных вариантов**) и для наибольшего корня (**для чётных вариантов**) заполнить табл. 3 при $ \varepsilon = 0.000001 $. Сделать выводы. | + | |
- | - Теоретически и экспериментально исследовать скорость сходимости и обусловленность метода. Сделать выводы. | + | |
- | - При решении системы уравнений $ F(X) = 0 $: | + | |
- | - Графически отделить решения системы нелинейных уравнений $ F(X) = 0 $. | + | |
- | - Составить подпрограммы для вычисления функций $ f_1(x, y) $ и $ f_2(x, y) $. Составить подпрограмму вычисления системы $ F(X) $. | + | |
- | - Для метода Ньютона: | + | |
- | - Составить программу ''newts()'' для вычисления решений системы уравнений методом Ньютона с заданной точностью $ \varepsilon $. | + | |
- | - Провести вычисления по программе для каждого корня. Заполнить табл. 4 при указанных значениях $ \varepsilon $. Сделать выводы. | + | |
- | - Для одного из корней заполнить табл. 5 при $ \varepsilon = 0.000001 $. Сделать выводы. | + | |
- | - Для метода простых итераций: | + | |
- | - Привести систему $ F(X) = 0 $ к виду $ X = \Phi(X) $ и проверить матрицу $ \Phi(X) $ на сходимость. Если сходимость не выполняется при любом преобразовании системы $ F(X) = 0 $ (необходимо это показать!), то привести матрицу $ \Phi(X) $ к виду $ \Phi(X) = X + \Lambda F(X) $, где $ \Lambda $ -- некоторая мажорирующая матрица. Составить программу ''Phi()'' для функции $ \Phi(X) $, удовлетворяющей сходимости. | + | |
- | - Составить программу ''siters()'' для вычисления решения системы уравнений методом простых итераций с заданной точностью $ \varepsilon $. | + | |
- | - Провести вычисления по программе для каждого корня. Заполнить табл. 3 при указанных значениях $ \varepsilon $. Сделать выводы. | + | |
- | - Для одного из корней заполнить табл. 6 при $ \varepsilon = 0.000001 $. Сделать выводы. | + | |
- | + | ||
- | ==== Таблицы ==== | + | |
- | === Таблица 1 === | + | |
- | ^ Значение $ \varepsilon $ ^ Значение $ x_1 $ ^ Значение $ x_2 $ ^ Число итераций $ k $ ^ | + | |
- | | 0.1 | | | | | + | |
- | | ... |||| | + | |
- | + | ||
- | === Таблица 2 === | + | |
- | ^ Значение $ k $ ^ Значение $ x^{(k)} $ ^ Значение $ f(x^{(k)}) $ ^ Значение $ f'(x^{(k)}) $ ^ Значение $ -f(x^{(k)})/f'(x^{(k)}) $ ^ | + | |
- | | 0 | | | | | | + | |
- | | ... ||||| | + | |
- | + | ||
- | === Таблица 3 === | + | |
- | ^ Значение $ k $ ^ Значение $ x^{(k)} $ ^ Значение $ \varphi(x^{(k)}) $ ^ | + | |
- | | 0 | | | | + | |
- | | ... ||| | + | |
- | + | ||
- | === Таблица 4 === | + | |
- | ^ Значение $ \varepsilon $ ^ Значение $ \vec r_1 = (x_1, y_1) $ ^ Значение $ \vec r_2 = (x_2, y_2) $ ^ Число итераций $ k $ ^ | + | |
- | | 0.1 | | | | | + | |
- | | ... |||| | + | |
- | + | ||
- | === Таблица 5 === | + | |
- | ^ Значение $ k $ ^ Значение $ \vec r^{(k)} $ ^ Значение $ f_1(\vec r^{(k)}) $ ^ Значение $ f_2(\vec r^{(k)}) $ ^ Значение $ -J^{-1}(\vec r^{(k)}) \cdot F(\vec r^{(k)}) $ ^ | + | |
- | | 0 | | | | | | + | |
- | | ... ||||| | + | |
- | + | ||
- | === Таблица 6 === | + | |
- | ^ Значение $ k $ ^ Значение $ \vec r^{(k)} $ ^ Значение $ \Phi(\vec r^{(k)}) $ ^ | + | |
- | | 0 | | | | + | |
- | | ... ||| | + | |
- | ===== Варианты заданий ===== | + | |
- | <note important> | + | |
- | Выполнение работ осуществляется по индивидуальным вариантам заданий (уравнений и систем уравнений). Номер варианта для каждого студента определяется преподавателем. | + | |
- | </note> | + | |
- | [[.task3:task3_vars]] | + | |
- | ===== Содержание отчёта ===== | + | |
- | * Цель работы. | + | |
- | * Краткое изложение основных теоретических понятий. | + | |
- | * Постановка задачи с кратким описанием порядка выполнения работы. | + | |
- | * Графическое или аналитическое решение уравнения. Обоснование выбора начального приближения. | + | |
- | * Необходимые рисунки и таблицы с краткими выводами. | + | |
- | * Теоретические скорости сходимости методов и их экспериментальное доказательство. Сравнение методов. | + | |
- | * Общий вывод по проделанной работе. | + | |
- | * Код программы. | + |