Метод удвоения шага и метод бисекции
Общая характеристика теоремы Больцеана-Коши. Знакомство с особенностями метода равномерного поиска и метода бисекции. Анализ основных проблем поиска интервалов, содержащих корень, с заданной степенью точности. Рассмотрение способов локализации отрезков.
| Рубрика | Математика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 02.10.2013 |
| Размер файла | 258,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1.Постановка задачи
шаг бисекция равномерный поиск
С заданной точностью найти интервал, на котором находится решение уравнения , используя метод удвоения шага и метод бисекции.
2. Краткие теоретические сведения
Решение уравнения f(x)=0 можно разбить на следующие подзадачи:
1) Определение количества корней данного уравнения;
2) Локализация отрезков, на которых находится по одному корню;
3) Поиск интервалов, содержащих корень, с заданной степенью точности.
Для определения количества корней данного уравнения можно применить теорему Больцеана-Коши.
Теорема Больцеана-Коши: если непрерывная на отрезке [a;b] функция на его концах имеет противоположные знаки (т.е., если f(a)*f(b)<0), то на [a;b] она хотя бы один раз обращается в ноль.
Затем необходимо локализовать отрезки, содержащие корень. На этом шаге можно применить следующую теорему:
Непрерывная строго монотонная функция f(x) на промежутке [a;b] имеет и притом в единственной точке значение 0 тогда и только тогда, когда на его концах она принимает значения разных знаков.
Локализацию отрезков можно проводить следующими способами:
1) Методом равномерного поиска;
2) Методом удвоения шага;
3) Методом половинного деления;
4) Методом хорд;
5) Методом Ньютона;
и другими.
После локализации отрезка необходимо проверить, имеет ли он указанную точность. Эта проверка проводится с помощью сравнения длины локализованного отрезка с наперёд заданной величиной е. Если длина отрезка меньше е, то можно идти на конец соответствующего алгоритма локализации.
3. Алгоритмы. Метод удвоения шага
Пусть некоторое число а задаёт начало поиска, а некоторое (достаточно большое) число b ограничивает число возможных итераций, и некоторое число h задаёт величину шага. Тогда алгоритм будет выглядеть следующим образом:
1) Пусть x0=a. Тогда x1:= x0+h.
2) Проверим неравенство f(xi+1)*f(xi)<0. Если оно верно, то идём к шагу 4). Иначе - к шагу 3);
3) xi+1:=xi+2i*h. Идём к шагу 2);
4) Если |xi+1-xi|<=h, то идём к шагу 5). Иначе x0:=xi, b:=xi+1, x1:= x0+h;
5) Если |xi+1-xi|<=е, то идём на конец алгоритма. Иначе уменьшаем h в нужное число раз и переходим к шагу 4)
4.Метод половинного деления
Пусть f(x) монотонна на промежутке [a;b], f(a)*f(b)<0, тогда:
1) с:=(a+b)/2;
2) Если f(a)*f(с)<0, то b:=с. Переход к шагу 4). Иначе - переход к шагу 3);
3) a:=с. Переходим к шагу 4)
4) Если (b-a)<=е, то идём на конец алгоритма. Иначе переходим к шагу 1).
5. Код программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, XPMan, ComCtrls, StdCtrls;
type
TForm1 = class(TForm)
edt1: TEdit;
edt2: TEdit;
ud1: TUpDown;
ud2: TUpDown;
xpmnfst1: TXPManifest;
lbl1: TLabel;
lbl2: TLabel;
mmo1: TMemo;
edt4: TEdit;
lbl4: TLabel;
ud4: TUpDown;
btn1: TButton;
btn2: TButton;
edt5: TEdit;
lbl5: TLabel;
procedure edt2Change(Sender: TObject);
procedure edt1Change(Sender: TObject);
procedure btn1Click(Sender: TObject);
procedure btn2Click(Sender: TObject);
procedure edt4Change(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var a,b,i,j:Integer; //нижняя и верхняя границы поиска + вспомогательные переменные
xa,x1,x2,xb,h,eps:Real; //Первоначальный шаг и заданная точность + вспомогательные переменные
Form1: TForm1;
implementation
{$R *.dfm}
function amount (x1, x2: real):real;
//Вычисление произведения значений функции в точках х1 и х2, чтобы потом определить его знак.
var am1, am2: Real;
begin
if x1=0 then x1:=1/eps; //Во избежание ошибки деления на ноль
am1:=Sqrt(1+x1)-(1/x1);
if x2=0 then x2:=1/eps;
am2:=Sqrt(1+x2)-(1/x2);
amount:=am1*am2;
if x1=1/eps then x1:=0;
if x2=1/eps then x2:=0;
end;
function equality (x1,x2,compa:real):Boolean; //compa = compared - сравнимая величина.
//Так как в силу специфики обработки компьютером чисел с плавающей точкой внезапно
var t:Real; //появляются миллиардные доли, мешающие сравнению, пришлось написать специальную функцию сравнения
begin
t:=10*eps;
if abs(x2-x1-compa)<1/t then equality:=true
else equality:=False;
end;
procedure TForm1.edt2Change(Sender: TObject);
begin
a:=StrToInt(edt1.Text); //Небольшой foolproof во избежание системных ошибок и нулевого числа срабатываний
b:=StrToInt(edt2.Text);
if a>=b then begin
ShowMessage ('Нижняя граница интервала не может быть меньше либо равна верхней!');
b:=a+1;
edt2.Text:=IntToStr(b);
end;
end;
procedure TForm1.edt1Change(Sender: TObject);
begin
a:=StrToInt(edt1.Text);
b:=StrToInt(edt2.Text);
if a>=b then begin
ShowMessage ('Нижняя граница интервала не может быть меньше либо равна верхней!');
//Небольшой foolproof во избежание системных ошибок и нулевого числа срабатываний
a:=b-1;
edt1.Text:=IntToStr(a);
end;
if a<-1 then begin
//А это - на случай, если кому вздумается ввести значение х, находящееся за пределами ОДЗ [-1; +inf)
ShowMessage('При x<(-1) функция не существует!');
a:=-1;
edt1.Text:=IntToStr(a);
end;
end;
procedure TForm1.btn1Click(Sender: TObject);
var found:Boolean; //Нашли ли мы промежуток с корнем?
begin
eps:=0.1;
for i:=0 to strtoint(edt4.Text) do eps:=eps*10;
a:=StrToInt(edt1.Text);
b:=StrToInt(edt2.Text);
h:=1;
if h>(b-a) then h:=(b-a)/2; //Небольшой foolproof на случай, если кому-то вздумается поставить шаг меньше, чем промежуток между a и b
xa:=a;
xb:=b;
j:=1;
x1:=xa;
x2:=xa+h;
while (x2<b) and (((equality(x1,x2,(1/eps)))=False) or (amount(x1,x2)>0)) do begin
//Зачем такое сложное условие? Да чтобы у меня: 1) Выводил "Нет корней", дойдя до верхней границы; 2) Не завершал сразу поиск, как только h=1/eps
if amount(x1,x2)<=0 then begin
found:=True;
if equality(x1,x2,h) then h:=h/10;
//Если разность между х2 и х1 равна h, и при этом х1 и х2 - границы интервала, содержащего корень, то уменьшаем h в десять раз для повышения точности
xa:=x1;
xb:=x2;
x2:=x1;
j:=1;
end;
x1:=x2;
x2:=x1+j*h;
j:=j*2;
if x2>xb then x2:=xb;
end;
if found=True then edt5.Text:='('+FloatToStr(x1)+' ; '+floattostr(x2)+')'
else edt5.Text:='В указанном промежутке нет корней';
end;
procedure TForm1.btn2Click(Sender: TObject);
var found:Boolean;
begin
eps:=0.1;
for i:=0 to strtoint(edt4.Text) do eps:=eps*10;
a:=StrToInt(edt1.Text);
b:=StrToInt(edt2.Text);
h:=(b-a)/2;
xa:=a;
xb:=b;
while (xb-xa)>1/eps do begin
//Тут простое условие, т.к. у нас нет такой величины, как размер шага.
if amount(xa,h)<0 then begin
xb:=h;
h:=(xa+xb)/2;
found:=true;
end
else if amount(h,xb)<0 then begin
xa:=h;
h:=(xa+xb)/2;
found:=true;
end
else begin
found:=False;
Break;
end;
end;
if found=True then edt5.Text:='('+FloatToStr(xa)+' ; '+floattostr(xb)+')'
else edt5.Text:='В указанном промежутке нет корней';
end;
procedure TForm1.edt4Change(Sender: TObject);
begin
if StrToInt(edt4.Text)>10 then begin
ShowMessage('Указанная степень точности слишком велика!');
edt4.Text:='10';
end;
end;
end
6. Тестовый пример
Рисунок 1 - вычисление интервала, содержащего корень, методом удвоения шага
Рисунок 2 - вычисление интервала, содержащего корень, методом бисекции
7. Проверка в MathCad
Рис.
1. Размещено на Allbest.ru
...Подобные документы
Общая постановка задачи. Отделение корня. Уточнение корня. Метод половинного деления (бисекции). Метод хорд (секущих). Метод касательных (Ньютона). Комбинированный метод хорд и касательных. Задания для расчётных работ.
творческая работа [157,4 K], добавлен 18.07.2007Описание метода сведения краевой задачи к задаче Коши. Решение системы из двух уравнений с четырьмя неизвестными. Метод Рунге-Кутта. Расчет максимальной погрешности и выполнение проверки точности. Метод конечных разностей. Описание полученных результатов.
курсовая работа [245,2 K], добавлен 10.07.2012Структура и принципы решения линейных уравнений. Метод Крамера и Гаусса, Ньютона, половинного деления, секущих. Отличительные особенности и условия применения графического метода. Содержание теоремы Штурма. Принципы и основные этапы поиска интервалов.
реферат [948,7 K], добавлен 30.03.2019Ознакомление с историей появления метода золотого сечения. Рассмотрение основных понятий и алгоритма выполнения расчетов. Изучение метода чисел Фибоначчи и его особенностей. Описание примеров реализации метода золотого сечения в программировании.
курсовая работа [416,0 K], добавлен 09.08.2015Сущность и графическое представление методов решения нелинейных уравнений вида F(x)=0. Особенности метода хорд, бисекции, простой итерации, касательных и секущих. Проверка результатов с помощью встроенных функций и оценка точности полученных значений.
контрольная работа [316,1 K], добавлен 09.11.2010Исторический процесс развития взглядов на существо математики как науки, основные этапы формирования аксиоматического метода. Теории групп, множеств, отображений и конгруэнтности (равенства) отрезков. Основные аксиоматические теоремы и их доказательства.
курсовая работа [26,2 K], добавлен 24.05.2009Математические модели явлений или процессов. Сходимость метода простой итерации. Апостериорная оценка погрешности. Метод вращений линейных систем. Контроль точности и приближенного решения в рамках прямого метода. Метод релаксации и метод Гаусса.
курсовая работа [96,7 K], добавлен 13.04.2011Задачи Коши и методы их решения. Общие понятия, сходимость явных способов типа Рунге-Кутты, практическая оценка погрешности приближенного решения. Автоматический выбор шага интегрирования, анализ брюсселятора и метод Зонневельда для его расчета.
курсовая работа [1,7 M], добавлен 03.11.2011Формулировки и доказательства китайской теоремы об остатках. Доказательство с помощью метода математической индукции. Конструктивный метод доказательства. Основные алгоритмы поиска решения. Применение китайской теоремы об остатках к открытию сейфа.
курсовая работа [1,0 M], добавлен 08.01.2022Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.
курсовая работа [716,1 K], добавлен 12.07.2012Контрольный пример к алгоритму метода хорд. Вычисление и уточнение корня методом хорд и касательных. Нахождение второй производной заданной функции. Уточненное значение корня решаемого уравнения на заданном интервале. Код программы данного примера.
лабораторная работа [276,9 K], добавлен 02.12.2014Геометрическая интерпретация методов Ньютона, итерации и спуска. Определение корня уравнения с заданной степенью точности. Решение систем нелинейных алгебраических уравнений. Нахождение эквивалентного преобразования для выполнения условия сходимости.
курсовая работа [371,6 K], добавлен 14.01.2015Вероятностное обоснование метода наименьших квадратов как наилучшей оценки. Прямая и обратная регрессии. Общая линейная модель. Многофакторные модели. Доверительные интервалы для оценок метода наименьших квадратов. Определение минимума невязки.
реферат [383,7 K], добавлен 19.08.2015Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Смысл метода Ньютона для решения нелинейных уравнений. Доказательства его модификаций: секущих, хорд, ложного положения, Стеффенсена, уточненного для случая кратного корня, для системы двух уравнений. Оценка качества метода по числу необходимых итераций.
реферат [99,0 K], добавлен 07.04.2015Классификация методов кластеризации и их характеристика. Метод горной кластеризации в Matlab. Возможная область применения кластеризации в различных предметных областях. Математическое описание метода. Пример использования метода на реальных данных.
реферат [187,0 K], добавлен 28.10.2010Теоретическое обоснование расчетных формул. Задача Коши для дифференциального уравнения первого порядка. Метод Рунге-Кутта. Ломаная Эйлера. Построение схем различного порядка точности. Выбор шага. Апостериорная оценка погрешности. Правило Рунге.
курсовая работа [111,1 K], добавлен 13.11.2011Применение метода дополнительного аргумента к решению характеристической системы. Доказательство существования решения задачи Коши. Постановка задачи численного расчёта. Дискретизация исходной задачи и её решение итерациями. Программа и её описание.
дипломная работа [5,7 M], добавлен 25.05.2014Знакомство с уравнениями линейной регрессии, рассмотрение распространенных способов решения. Общая характеристика метода наименьших квадратов. Особенности оценки статистической значимости парной линейной регрессии. Анализ транспонированной матрицы.
контрольная работа [380,9 K], добавлен 05.04.2015Общая схема методов спуска. Метод покоординатного спуска. Минимизация целевой функции по выбранным переменным. Алгоритм метода Гаусса-Зейделя. Понятие градиента функции. Суть метода наискорейшего спуска. Программа решения задачи дискретной оптимизации.
курсовая работа [90,8 K], добавлен 30.04.2011
