- •Вычислительная математика лабораторный практикум
- •Содержание
- •Метод исключения Гаусса
- •Введение
- •Построение алгоритма исключения Гаусса
- •3. Реализация алгоритма Гаусса в Excel
- •4. Реализация алгоритма Гаусса в пакете Mathcad
- •5. Реализация алгоритма Гаусса на языке Turbo Pascal
- •6. Вычисление определителя и обратной матрицы
- •7. Выбор ведущего элемента
- •8. Числа обусловленности
- •9. Задания для самостоятельной работы
- •Контрольные вопросы
- •1.Введение
- •Метод Якоби для решения слау
- •Метод Зейделя для решения слау
- •Задания для самостоятельной работы
- •5. Контрольные вопросы
- •Численные методы решения нелинейных уравнений
- •1. Введение
- •2. Отделение корней уравнения
- •3. Метод дихотомии для решения нелинейных уравнений
- •4. Метод Ньютона для решения нелинейных уравнений
- •5. Задания для самостоятельной работы
- •6. Контрольные вопросы
- •Полиномиальная интерполяция
- •1. Интерполяция данных каноническим полиномом
- •2. Интерполяционный полином Ньютона
- •3. Интерполяционный полином Лагранжа
- •4. Задания для самостоятельной работы
- •Контрольные вопросы
- •Метод наименьших квадратов
- •1. Введение
- •2. Линейная аппроксимация
- •3. Аппроксимация нелинейными функциями
- •4. Аппроксимация полиномом
- •Задания для самостоятельной работы
- •6. Контрольные вопросы
- •1. Введение
- •2. Постановка задачи
- •3. Численное дифференцирование с заданной точностью
- •Модификация алгоритма численного дифференцирования Использование центральной разности (6.3) для приближения производной позволяет проводить вычисления с точность порядка :
- •Результаты вычислений сведем в таблицу:
- •5. Действия над приближенными числами
- •6. Задания для самостоятельной работы
- •Контрольные вопросы
- •1. Введение
- •2. Метод прямоугольников
- •3. Метод трапеций
- •4. Метод парабол
- •5. Вычисление интегралов с заданной точностью
- •Метод Гаусса
- •7. Задания для самостоятельной работы
- •2. Провести расчеты знакомого уже нам интеграла ошибок
- •8. Контрольные вопросы
- •Список литературы
- •Учебное издание
2. Отделение корней уравнения
Для отделения действительных корней полезно заранее определить верхние и нижние границы их расположения. Для этого используем следующую методику вычислений.
Кольцо, в котором расположены корни уравнения, вычисляют по следующей формуле:
r ≤ | x*i| ≤ R , (3.8)
где x*i - точные корни уравнения,
, ,
А = max , B = max .
Соответственно положительные корни будут находиться на интервале:
r < x*i+ < R ,
а отрицательные:
- R < x*i ¯ < - r.
Также интервал расположения корней можно определить графически. Приведем пример отделения корней для уравнения .
По формуле (3.8) кольцо, в котором расположены корни, будет [0.714 , 6]. Отсюда, положительные корни находятся на отрезке [0.714 , 6], а отрицательные – [-6 , -0,714]. Для уточнения границ отрезков можно построить график (рис.3.1.)
Рис. 3.1. График функции
Из рис.3.1. видно, что интервал для положительного корня можно сузить до отрезка [1 , 3]. Для дальнейшего вычисления положительного корня уравнения будем использовать полученный отрезок.
3. Метод дихотомии для решения нелинейных уравнений
Рассмотрим простейший метод уточнения значения корня с заданной точностью - метод деления отрезка пополам (дихотомии или бисекций). Если определен интервал нахождения корня [a,b], то этот алгоритм состоит из:
Задания значений и вычисления значений функции на концах отрезка u=f(a), v=f(b).
Организации цикла, в котором последовательно выбранный отрезок делится пополам и осуществляется выбор того из двух отрезков, на котором функция меняет знак.
Выбор нужного отрезка можно реализовать так. Определяется середина отрезка и значение функции в этой точке w=f(x). Если произведение функций u*w < 0 , то интервал [a,b] сужается справа заменой b=x, v=w, иначе - слева заменой a=x, u=w . Изобразите данные ситуации на графике и разберитесь с предлагаемым способом выбора требуемого отрезка.
Реализацию метода дихотомии можно провести в Excel. Рассмотрим методику на примере уравнения . Начальный интервал неопределенности отрезок [1 , 3], заданная точность =0,001. Для нахождения приближенного корня уравнения понадобилось выполнить 19 шагов.
Таблица 1. Вспомогательная таблица для вычисления корней нелинейного уравнения методом дихотомии
Решение уравнения можно произвести в пакете Mathcad . Ниже приведена функция для вычисления корней методом дихотомии в данном пакете.
Корень уравнения с использованием данной функции будет следующим 2.094551 и достигнут за 34 шага.
На языке Pascal для решения уравнения методом дихотомии необходимо использовать несколько подпрограмм-функций
function X_Dich(a,b,eps:real):real;
var u,v,wx:real;
begin
u:=f(a); v:=f(b);
repeat
x:=0.5*(a+b); w:=f(x);
if (u*w<0.0)
then begin b:=x; v:=w end
else begin a:=x; u:=w end;
until abs(w) < eps;
X_Dich:=x
end;
Здесь цикл заканчивается при условии, что функция f(x) попадает «в полосу шума» .
Выбор нужного отрезка можно осуществить и с помощью знаковой функции Sign(x): равной единице, если x>0, минус единице, если x<0 и нулю, если x=0.
function Sign(x:real):integer;
begin
Sign:=0;
If x<0.0 then Sign:=-1;
If x>0.0 then Sign:= 1;
end;
При уменьшении интервала [a,b] точка a всегда остается слева от искомого корня и знак функции f(a) не изменяется. Поэтому в процессе половинного деления можно сравнивать его со знаком функции f(x). При их совподении точку a передвигаем в середину отрезка, в противном случае передвигаем точку b.
function X_Dich(a,b,eps:real):real;
var s:integer; w:real;
begin s:=Sign(f(a));
repeat
x:=0.5*(a+b); w:= f(x);
if Sign(w)=s
then a:=x
else b:=x;
until abs(w) < eps;
X_Dich:=x
end;
Использование знаковой функции наглядно показывает, что в методе половинного деления поведение функции f(x) употребляется пассивно, оно влияет только на выбор нужного интервала.
Изучите приведенные алгоритмы, проведите отладку программы и сделайте её тестирование. В качестве теста используйте любое уравнение с известным решением. В частности, можно рекомендовать уравнение Валлиса , имеющего один вещественный корень 2.09455.
Подпрограмму можно улучшить, вводя новый тип
Type fun=function(x:real):real; {$F+}
и изменив заголовок функции
function X_Dich(a,b,eps:real;f:fun):real;
Теперь можно использовать названия других функций левой части урвнения (3.1), не делая изменений в подпрограмме X_Dich.
Рекомендуется обезопасить подпрограмму от возможного «зацикливания», установив счетчик и соответствующие условия, например так:
if k>kmax
then begin writeln(‘Error01’); Exit end;
Введение счетчика полезно так же и при проведении вычислительных экспериментов по определению числа итераций, требуемых для достижения различной точности, наример, , изучении условий остановки цикла (3.4,3.5), сравнении различных методов уточнения корня и др.
Полезно в своей библиотеке иметь не только подпрограммы-функции, но и процедуры, составленные на основе приведенных алгоритмов. Напишите их, выполните отладку и тестирование.
Приведем рекурсивный вариант метода дихотомии:
function X_Dich(a,b,eps:real):real;
var x:real;
begin
if keypressed then Halt;
if f(a)*f(b) > 0.0
then begin writeln(Error02); Exit end
else begin x:=0.5*(a+b);
if abs(f(x)) > eps
then if f(a)*f(x) <0.0
then X_Dich:=X_Dich(a,x,eps)
else X_Dich:=X_Dich(x,b,eps)
else X_Dich:=x
end
end;
Изучите его, проведите отладку и тестирование программы, сделайте сравнение.
Выбор очередной точки в середине отрезка не является единственным вариантом. Можно в качестве такой точки выбрать случайное число, заменив оператор x:=0.5*(a+b) на
x:=a+(b-a)*random, предварительно инициализируя датчик случайных чисел Randomise. Проведите соответствующие расчеты и сравните требуемое число итераций для достижения заданной точности.
Б олее совершенный метод выбора точки деления отрезка [a,b] – метод хорд, в котором в качестве x выбирается точка пересечения с осью абсцис прямой y=Ax+B (хорды), проведенной через концы интервала u=f(a) и v=f(b).
a b x
u
Рис. 3.2. Графическая иллюстрация метода хорд
Из рисунка видно, что
, где . (3.9)
Описанные методы являются линейно сходящимися или, как говорят, сходящимися со скоростью геометрической прогрессии. В самом деле, абсолютные погрешности связаны соотношением , где знаменатель С=0.5. Метод половинного деления имеет среднюю скорость сходимости равную ln2, в то время как метод хорд в зависимости от свойств функции может иметь как меньшую, так и большую среднюю скорость сходимости. Рекомендуется исследовать этот вопрос экспериментально.