26801

Методы отделения корней уравнения

Реферат

Информатика, кибернетика и программирование

Чтобы отделить корень графически необходимо построить график функции fx на промежутке изменения x тогда абсцисса точки пересечения графика функции с осью ОХ есть корень уравнения. Этот метод можно получить из метода Ньютона заменив производную f'x отношением разности функции к разности аргумента в окрестности рассматриваемой точки f 'x fxh fx h. Подставляя это выражение в xk1 = xk fxk f 'xk получим xi1 = xi fxih fxihfxi 1 Геометрически это означает что приближенным значением корня считается точка...

Русский

2013-08-18

136.17 KB

28 чел.

1. Методы отделения корней уравнения.

Отделение корней можно осуществить аналитическим и графическим способами:

I. Чтобы отделить корень аналитически, достаточно найти такой отрезок  [a, b], на котором выполняются 3 условия:

1) f (a)*f(b) <0

2) f (x) – непрерывная на  [a , b] функция

3) f (x) – монотонная на [a , b] функция.

II. Чтобы отделить корень графически, необходимо построить график функции f(x) на промежутке изменения x, тогда абсцисса точки пересечения графика функции с осью ОХ есть корень уравнения.

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

2. Уточнение корней уравнения. Метод деления отрезка пополам, метод секущих.

Уточнить корень – значит найти его приближенное значение с заданной погрешностью e.

Самый простой метод, пригодный для любых непрерывных функций – метод деления отрезка пополам. Это самый простой метод вычисления корня уравнения. Разделим исходный отрезок [a,b] пополам  c=(a+b)/2 .

Проверяя знаки f(a), f(b), f(c) выясним в каком из отрезков [a,c] или [c,b] содержится корень

x* є [a,c] , если f(a)f(c)<0 ;

x* є [c,b] , если f(c)f(b)<0 .

 Выбранный отрезок принимаем за [a,b] и повторяем это до тех пор пока получаемый отрезок не сожмется до заданной степени точности. При n итерациях получим соотношение (b-a)/2n <= e, из которого можно вычислить число итераций, необходимое для достижения заданной степени точности n>= ln2(b-a)/e .

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

Метод секущих. Этот метод можно получить из метода Ньютона заменив производную f'(x) отношением разности функции к разности аргумента в окрестности рассматриваемой точки

f '(x) ~( f(x+h) - f(x))/h.

Подставляя это выражение в xk+1 = xk - f(xk)/f '(xk) получим

xi+1 = xi - f(xi)h / (f(xi+h)-f(xi))   (1)

Геометрически это означает, что приближенным значением корня считается точка пересечения секущей, проходящей через две точки функции f(xi) и f(xi+h), с осью абсцисс.

При использовании этого метода следует уменьшать величину h по мере приближения к корню.

Вариацией этого метода является метод ложных положений. В нем для проведения секущей используются текущая и предыдущая точки. Первое приближение вычисляется по формуле (1), а остальные по формуле xi+1 = xi - f(xi)(xi-1 - xi) /(f(xi-1) -f(xi)).

3. Уточнение корней уравнения. Методы касательных (Ньютона).

f(x)=0. Предположим, что f(x) имеет корень с на отрезке [a,b] и дифференцируема на этом отрезке, причём f’(x) не обращается в нуль.

Возьмём произвольную точку x0[a,b] и запишем в этой точке уравнение касательной y=f(x0)+f’(x0)(x-x0).

Графики функций f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью ОХ будет находиться недалеко от корня с. Для определения точки x1 имеем уравнение:

f(x0)+f’(x0)(x1-x0)=0

Повторим проделанную процедуру: написав уравнение касательной графика функции f(x) при x=x1 и найдя точку пересечения x2 с осью ОХ, получим

Продолжая этот процесс, получаем:

Достаточные условия сходимости метода касательных: пусть f(x) определена и дважды дифференцируема на отрезке [a,b], причем f(a)*f(b)<0, и производные f’(x) и f’’(x) сохрняют постоянный знак на отрезке [a,b], тогда исходя из начального приближения x0[a,b], удовлетворяющего неравенству f(x0)*f’’(x0)>0, можно построить последовательность
, сходящуюся к единственному на [
a,b] решению уравнения f(x)=0.

Геометрическая интерпретация такова: если через точку с координатами (xn,f(xn)) провести касательную, то абсцисса точки пересечения касательной с осью ОХ есть очередное приближение xn+1 к корню уравнения.

Итерационный процесс можно прекращать, если .

4. Аппроксимация функций.

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

Функция f(xi) называется аппроксимируемой.

Функция Q(x) называется аппроксимирующей.

Классической теорией приближения Q(x) выбирают в классе степенных многочленов.

Таким образом,будем рассматривать аппроксимацию функции yi=f(xi),i=0,n полиномом степени m.

Qm(x)=a0+a1x+…+anxm, mn.

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

5. Квадратичная аппроксимация (МНК).

МНК заключается в том, чтобы построить такой полином Qm(x)=, что сумма квадратичных отклонений значений аппроксимируемой и аппроксимирующей функций, называемая квадратичным отклонением, в узлах была бы минимальной.

Очевидно, что минимума квадратичного отклонения Φ можно добиться засчёт изменения коэффициентного полинома Qm(x) a0, am. Условием минимума является равенство 0 частных производных по всем коэффициентам a0,…,am. Это дает систему m+1 уравнения с m+1 неизвестным.

Раскрывая скобки и выполняя суммирования получаем:

++…+am

Система представляет собой СЛАУ относительно коэффициента аi . Решив систему, построим полином Qm(x), аппроксимирующий функцию yi=f(xi) и минимизирующий квадратичное отклонение.

Можно доказать, что если среди точек х1, х2,…, xn нет совпадающих, mn, то определитель системы отличен от нуля, следовательно, система имеет единственное решение.

Замечание: Функция Q(x) необязательно должна быть представлена полиномом вида . Единственным критерием выбора этой функции является возможность минимизации суммы квадратов отклонений. Как правило, используют аппроксимирующий полином не выше 3-ей степени.

{ - разность между аппроксимируемой и аппроксимирующей функциями.

Мы минимизируем сумму площадей квадратов, построенных на разности.

6. Интерполяция функций. Интерполяционный полином Лагранжа.

Пусть задано несовпадающее множество точек xi, которое мы будем называть узлами и в которых известны значения f(xi), i=0,n.

  1.  Способ построения аппроксимирующей функции, при котором в узлах значения аппроксимирующей и аппроксимируемой функции совпадают, называется интерполяцией.
  2.  Интерполяция – это частный случай аппроксимации, когда аппроксимирующая прямая проходит через точки таблицы.

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

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

Пусть m=n, тогда коэффициенты ai можно определить из системы уравнений:

Определитель той системы – есть определитель Вандермонда:

Система имеет единственное решение, т.к. ∆≠0.

Полином Q(x)=Ln(x), коэффициенты которого определяются из этой системы, называется интерполяционным полиномом Лагранжа и может быть записан в виде:

m=n, где m – степень полинома, n – число узлов+1. Следовательно, степень полинома должна быть на 1 меньше числа узлов.

 

7. Численное дифференцирование.

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

Итак, пусть в точках xi, i=0,1,2,...n известны значения функции yi=f(xi). Способ построения формул численного дифференцирования состоит в том, что по табличным точкам строится интерполянт Pn(x), который дифференцируется нужное число раз, и делается допущение о том, что производная от функции приблизительно равна производной от интерполянта

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

8. Численное интегрирование. Геометрический смысл численного интегрирования.

Задача численного интегрирования состоит в нахождении приближенного значения определенного интеграла от функции, заданной в виде таблицы.

Метод прямоугольников

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

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

Аппроксимация в этом методе осуществляется полиномом первой степени.

Метод Симпсона

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

9. Простейшие формулы численного интегрирования.

Квадратурная формула левых прямоугольников

Очевидно, что ее алгебраическая степень точности d=0 и формула является интерполяционной.

Квадратурная формула правых прямоугольников

Квадратурная формула средних прямоугольников

Алгебраическая степень точности d=1 и формула является интерполяционной.

Квадратурная формула трапеций

Квадратурная формула Симпсона

 

10. Обобщение простейших формул численного интегрирования.

?

11. Задача Коши для обыкновенного дифференциального уравнения 1-го порядка.

Задача Коши для обыкновенного дифференциального уравнения состоит в том, чтобы найти решение уравнения y' = f(x, y)   (2)   , удовлетворяющее начальным условиям

y(x0) = y0. (3)

Решение задачи Коши называется частным решением уравнения (2) при условии(3). Частному решению соответствует одна из интегральных кривых, проходящих через точку (x0,y0).

Будем искать приближенное решение этой задачи на конечном множестве точек отрезка [a, b], называемом сеткой:

xi = x0 + ih, x0 = a, xn = b,

h = (b-a)/n, i = 0,1,2,...,n.

Приближенным решением задачи будет некоторая сеточная функция y = y (x).

      Для получения значений сеточной функции используются различные методы основанные на замене производной каким-либо разностным уравнением.

12. Метод Эйлера решения задачи Коши для ОДУ 1-го порядка.

Простейшим численным методом решения задачи Коши является метод ломанных Эйлера. Суть метода Эйлера заключается в замене функции y(x) на отрезке интегрирования прямой линией, касательной к графику в точке x=xi. Если искомая функция сильно отличается от линейной на отрезке интегрирования, то погрешность вычисления будет значительной. Ошибка метода Эйлера прямо пропорциональна шагу интегрирования:

13. Одномерные задачи оптимизации.

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

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

2. численные методы

3. графические методы

Функция f(x), заданная на axb называется унимодальной на отрезке [a,b], если существует единственная точка x* минимума f(x), т.е. f(x*)= и если для любых двух точек x1, x2[a,b] выполняются условия: f(x1)>f(x2), что следует из неравенства x1<x2x* и f(x1)<f(x2), что следует из неравенств x2>x1x*.

Метод дихотомии

Пусть задана унимодальная функция f(x). Необходимо найти минимум функции на отрезке [a,b], которому принадлежит точка локального минимума x*. Для сужения отрезка унимодальности используем точки x1, x2, расположенные симметрично относительно середины отрезка [a,b].

Пусть известен отрезок [an-1;bn-1], находим середину отрезка:

Вычисляем значения функции в точках xn±δ, сравниваем их:

1) если f(xn-δ)<f(xn+δ), то an=an-1, bn=xn

2) если f(xn-δ)>f(xn+δ), то an= xn-δ, bn=bn-1

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

Метод золотого сечения

Золотое сечение, открытое Евклидом, состоит в разбиении интервала [a,b] на 2 части точкой x1 таким образом, чтобы отношение длины всего отрезка к большей части было равно отношению большей части к меньшей.

Коэффициент дробления отрезка [ a , b ] :

x1=b+(1-k)(b-a)

x2=b+k(b-a)

a       x1                x2             b

Алгоритм:

1) вычисляем значения x1, x2

2) вычисляем значения f(x1), f(x2)

3) проверяем условия:

- если f(x1)≤ f(x2), то для дальнейшего деления оставляют интервал [a,x2]

- если f(x1)> f(x2), то для дальнейшего деления оставляют интервал [x1,b]

Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности ε.Замечание: x1 производит золотое сечение интервала [a,x2], x2 – золотое сечение отрезка [x1,b].

14. Многомерные задачи оптимизации.

Пусть f(x1, x2,…, xn) – целевая функция. Задача поиска максимума этой функции сводится к минимизации функции - f(x1, x2,…, xn), поэтому будем рассматривать задачу поиска минимума. Наибольшие трудности поиска минимума f(x) возникают, когда размерность n вектора x велика, поэтому важнейшей проблемой является уменьшение размерности вектора целевой функции на этапе построения математической модели. В модели следует сохранить только те xi, которые сильнее других влияют на изменение целевой функции.

Линиями уровня f(x1, x2) называют семейство линий плоскости R2, на которых функция принимает постоянное значение.

Неявным уравнением линии уровня является уравнение вида f(x1, x2)=с.

Если функция f(x) имеет единственную точку минимума x*(x1*, x2*), то функция называется мономодальной и линии уровня имеют следующий вид:

 

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

Идея всех методов спуска состоит в том, чтобы из начального приближения точки x(0)=(x1(0), x2(0),…, xn(0)) перейти в точку x(1)=(x1(1), x2(1),…, xn(1)) такую, чтобы f(x(0))> f(x(1)).

Пусть в области D задано нулевое приближение x(0). Фиксируем значение x2(0),x3(0),…, xn(0) и рассматриваем функцию f(x1, x2(0),…, xn(0)) как функцию одной переменной x1. Находим минимум этой функции . Пусть x1(1) доставляет минимум этой функции. f(x1(1), x2(0),…, xn(0))≤ f(x1(0), x2(0),…, xn(0)).

Далее фиксируем значения x3(0),x4(0),…, xn(0) и рассматриваем функцию

f(x1(1), x2,x3(0),…, xn(0)) как функцию одной переменной x2 и т.д.

После n шагов получим f(x1(1), x2(1),x3(1),…, xn(1))≤ f(x1(0), x2(0),x3(0),…, xn(0)).

В результате первого шага покоординатного спуска происходит переход из начальной точки x0 в точку x1.

1) если f(x(0))= f(x(1)), то x(0) – точка минимума f(x).

2) если f(x(0))> f(x(1)), то выполняется следующий шаг покоординатного спуска, в котором за начальную точку принимается x(1).

Этот процесс продолжается до тех пор, пока f(x(k+1))-f(x(k))<ε, где ε – заданная  точность.

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

Численные методы отыскания минимума состоят в построении последовательности векторов {x(k)}, удовлетворяющих условию f(x(0))> f(x(1))>…> f(x(k)). В этих методах элементы последовательности вычисляются по формуле x(k+1)=x(k)+hk*(k), где (k) – направление спуска, hk – длина шага в этом направлении.

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

Используя антиградиент в качестве направления спуска, приходим к итерационному процессу вида:

      (1)

Все методы спуска, в которых вектор (k) совпадает с антиградиентом, называются градиентными методами.

Для минимизации функции используется метод градиентного спуска с дроблением шага. Процесс (1) с дроблением шага протекает следующим образом: выбираем некоторое значение x(0), затем выбираем hk=h=const и на каждом шаге процесса выбираем условие монотонности f(x(k+1))<f(x(k)). Если это условие нарушается, то h дробим до тех пор, пока монотонность не восстановится.

Для окончания счета можно использовать критерии:

Наиболее важным моментом в этом методе  - это выбор шага. Формула (1) с постоянным шагом практически не применяется.

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

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

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

,

т.е. на каждом шаге решается задача минимизации.

15. Задачи линейного программирования.

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

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

Среди ограничений часто встречаются условия неотрицательности всех или части переменных:


 

А также другие работы, которые могут Вас заинтересовать

34589. ОСНОВНЫЕ ФАКТОРЫ РОССИЙСКОГО ИСТОРИЧЕСКОГО ПРОЦЕССА 19.56 KB
  Самобытность России во многом определяется ее географическим положением между Европой и Азией – миром модернизации и миром традиционности. Этот фактор накладывает отпечаток на историческое развитие России. В самой России начиная с XVIII в. Главным среди природных факторов был континентальный характер расположения территории России.
34590. МЕСТО РОССИИ СРЕДИ МИРОВЫХ ЦИВИЛИЗАЦИЙ 24 KB
  МЕСТО РОССИИ СРЕДИ МИРОВЫХ ЦИВИЛИЗАЦИЙ Составитель: С. Соответственно и место России во всемирной истории определялось с точки зрения принадлежности ее к одной из общественноэкономических формаций.К какому же типу отнести Россию В какой мере самобытна цивилизация России Ответы на эти вопросы давались историками публицистами общественными деятелями с высоты своего времени с учетом всего предшествующего развития России а также в соответствии со своими идейнополитическими установками. Абсолютное большинство населения России исповедует...
34591. ВОСТОЧНЫЕ СЛАВЯНЕ В ДОФЕОДАЛЬНЫЙ ПЕРИОД 22.91 KB
  ВОСТОЧНЫЕ СЛАВЯНЕ В ДОФЕОДАЛЬНЫЙ ПЕРИОД Составитель: Л. Степанова Появление славян как самостоятельного этноса согласно археологическим материалам произошло еще в первое тысячелетие до н. славяне известны под именем антов и венедов. в источниках появляется имя славяне.
34592. ДРЕВНЕРУССКОЕ ГОСУДАРСТВО: ЗАКОНОМЕРНОСТИ И ОСОБЕННОСТИ ОБРАЗОВАНИЯ, СОЦИАЛЬНЫЙ И ПОЛИТИЧЕСКИЙ СТРОЙ (IX – начало XII вв.) 21.55 KB
  Но произошло это объединение в результате похода князя Олега датируемого летописью 882 годом при активном участии его Руси – варяжской дружины вместе с другими племенами Поильменья. Рассматривая особенности политического устройства Киевской Руси следует выделить такой родоплеменной пережиток как наследование великого княжения по старшинству. Это заставляло всю многочисленную родню Рюриковичей время от времени менять свое пребывание в одном из княжеств и перебираться в другое что не способствовало ни укреплению центральной власти в Киеве...
34593. США во Второй мировой войне 14.25 KB
  Когда УВП не удалось взять под свой контроль добычу и поставки сырья Рузвельт создал сначала управление экономической стабилизации а затем управление военной мобилизации наделенное чуть ли не диктаторскими полномочиями. Комиссия по справедливому найму которую Рузвельт был вынужден создать под угрозой негритянского марша на Вашингтон во главе с Филипом Рэндолфом председателем профсоюза железнодорожных проводников помогла афроамериканцам бороться с дискриминацией в военной промышленности особенно после того как в 1943 Рузвельт наделил...
34594. США в конце XX – начале XXI вв 15.84 KB
  Укрепление политического экономического военного лидерства в мире стало ведущей идеей политики США во второй половине XX начале XXI в. Этому способствовало с одной стороны ключевое положение США в ООН в составе 5 государств членов Совета Безопасности а с другой активное участие в создании НАТО сети других военнополитических блоков. Была развернута сеть военных баз и объектов США в Европе в государствах участниках НАТО на Дальнем Востоке и в бассейне Тихого океана в Латинской Америке и зоне Карибского бассейна на Ближнем...
34595. Соединенное Королевство: географическое положение, рельеф, природные условия, флора и фауна. Символы 40.5 KB
  Официально же она именуется Соединенное Королевство Великобритании и Северной Ирландии. В целом на их долю приходится приблизительно 1 3 площади Великобритании и бoльшая часть Северной Ирландии. В Северной Ирландии змей нет. Символы: Флаг Соединенного Королевства Великобритании и Северной Ирландии или как его принято называть Юнион Джек Union Jck является сочетанием трех крестов святых покровителей Англии прямой красный крест на белом поле крест Св.
34596. Столетняя война 17.15 KB
  Столетняя война наименование длительного военного конфликта между Англией и Францией 13371453 вызванного стремлением Англии вернуть принадлежавшие ей на континенте Нормандию Мен Анжу и др. а также династическими притязаниями английских королей на французский престол. война между Англией и Францией. причины войны: стремление Франции вытеснить Англию с югозапада страны провинция Гиень и ликвидировать этот последний оплот английской власти на франц.
34597. Династия Тюдоров. Генрих VII 19.17 KB
  Генрих VII Генрих VII Тюдор 28 января 1457 – 21 апреля 1509 – король Англии и государь Ирландии 1485 – 1509. Родители: Эдмунд Тюдор 1й граф Ричмонд; единоутробный брак короля Генриха VI Маргарита Бофорт. 1471 – гибель Генриха VI и принца Уэльского Генрих – почти единственный родственник Ланкастеров. Генрих поклялся в Ренне в случае захвата власти жениться на дочери Эдуарда IV Елизавете Йоркской.