Darbe.ru

Быт техника Дарби
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод хорд

Метод хорд

Пусть дано уравнение f(x) = 0, где f(x) — непрерывная функция, имеющая в интервале (a, b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a, b].

Идея метода хорд состоит в том, что на достаточно малом промежутке [a, b] дугу кривой y = f(x) можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай (рис. 1), когда первая и вторая производные имеют одинаковые знаки, т.е. f ‘(x)f ²(x) > 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

.

Приближение корня x = x1, для которого y = 0, определяется как

.

Аналогично для хорды, проходящей через точки A1 и B, вычисляется следующее приближение корня

.

В общем случае формула метода хорд имеет вид:

. (2)

Если первая и вторая производные имеют разные знаки, т.е.

то все приближения к корню x* выполняются со стороны правой границы отрезка [a, b], как это показано на рис. 2, и вычисляются по формуле:

. (3)

Выбор формулы в каждом конкретном случае зависит от вида функции f(x) и осуществляется по правилу: неподвижной является граница отрезка [a, b] изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (2) используется в том случае, когда f(b)f «(b) > 0. Если справедливо неравенство f(a)f «(a) > 0, то целесообразно применять формулу (3).

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

.

Тогда условие завершения вычислений записывается в виде:

, (4)

где e — заданная погрешность вычислений. Необходимо отметить, что при отыскании корня метод хорд нередко обеспечивает более быструю сходимость, чем метод половинного деления.

4. Метод Ньютона (касательных)

Пусть уравнение (1) имеет корень на отрезке [a, b], причем f ‘(x) и f «(x) непрерывны и сохраняют постоянные знаки на всем интервале [a, b].

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной. Для этого выбирается некоторое начальное приближение корня x0 на интервале [a, b] и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) до пересечения с осью абсцисс (рис. 3). Уравнение касательной в точке C0 имеет вид

y = f(x0) + f ‘(x0)×(x — x0).

Далее за приближение корня принимается абсцисса x1, для которой y = 0:

Затем проводится касательная через новую точку C1(x1, f(x1)) и определяется точка x2 ее пересечения с осью 0x и т.д. В общем случае формула метода касательных имеет вид:

В результате вычислений получается последовательность приближенных значений x1, x2, . xi, . каждый последующий член которой ближе к корню x*, чем предыдущий. Итерационный процесс обычно прекращается при выполнении условия (4).

Начальное приближение x0 должно удовлетворять условию:

В противном случае сходимость метода Ньютона не гарантируется, так как касательная будет пересекать ось абсцисс в точке, не принадлежащей отрезку [a, b]. На практике в качестве начального приближения корня x0, обычно выбирается одна из границ интервала [a, b], т.е. x0 = a или x0 = b, для которой знак функции совпадает со знаком второй производной.

Метод Ньютона обеспечивает высокую скорость сходимости при решении уравнений, для которых значение модуля производной ½f ¢(x)½вблизи корня достаточно велико, т.е. график функции y = f(x) в окрестности корня имеет большую крутизну. Если кривая y = f(x) в интервале [a, b] почти горизонтальна, то применять метод касательных не рекомендуется.

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

, (7)

т.е. значение производной достаточно вычислить только один раз в начальной точке. Геометрически это означает, что касательные в точках Ci(xi, f(xi)), где i = 1, 2, . заменяется прямыми, параллельными касательной, проведенной к кривой y = f(x) в начальной точке C0(x0, f(x0)), как это показано на рис. 4.

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

5. Метод простой итерации

Чтобы применить этот метод для решения уравнения (1) необходимо преобразовать его к виду . Далее выбирается начальное приближение и вычисляется x1, затем x2 и т.д.:

x1 = j(x0); x2 = j(x1); …; xk = j(xk-1); .

нелинейный алгебраический уравнение корень

Полученная последовательность сходится к корню при выполнении следующих условий:

1) функция j(x) дифференцируема на интервале [a, b].

2) во всех точках этого интервала j¢(x) удовлетворяет неравенству:

0 £ q £ 1. (8)

При таких условиях скорость сходимости является линейной, а итерации следует выполнять до тех пор, пока не станет справедливым условие:

.

,

может использоваться только при 0 £ q £ ½. Иначе итерации заканчиваются преждевременно, не обеспечивая заданную точность. Если вычисление q затруднительно, то можно использовать критерий окончания вида

; .

Возможны различные способы преобразования уравнения (1) к виду . Следует выбирать такой, который удовлетворяет условию (8), что порождает сходящийся итерационный процесс, как, например, это показано на рис. 5, 6. В противном случае, в частности, при ½j¢(x)½>1, итерационный процесс расходится и не позволяет получить решение (рис. 7).

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

Читайте так же:
Можно ли восстановить свидетельство об окончании автошколы

Список использованных источников

1. Алексеев В. Е., Ваулин А.С., Петрова Г. Б. — Вычислительная техника и программирование. Практикум по программированию :Практ .пособие/ -М.: Высш. шк. , 1991. — 400 с.

2. Абрамов С.А., Зима Е.В. — Начала программирования на языке Паскаль. — М.: Наука, 1987. -112 с.

3. Вычислительная техника и программирование: Учеб. для техн. вузов/ А.В. Петров, В.Е. Алексеев, А.С. Ваулин и др. — М.: Высш. шк., 1990 — 479 с.

4. Гусев В.А., Мордкович А.Г. — Математика: Справ. материалы: Кн. для учащихся. — 2-е изд. — М.: Просвещение, 1990. — 416 с.

ЛАБОРАТОРНАЯ РАБОТА 7 РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДАМИ БИСЕКЦИИ, НЬЮТОНА (КАСАТЕЛЬНЫХ, ХОРД, СЕКУЩИХ), ПРОСТОЙ ИТЕРАЦИИ I.

3 ЛАБОРАТОРНАЯ РАБОТА 7 РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДАМИ БИСЕКЦИИ, НЬЮТОНА (КАСАТЕЛЬНЫХ, ХОРД, СЕКУЩИХ), ПРОСТОЙ ИТЕРАЦИИ I. ЦЕЛЬ РАБОТЫ.Изучение основных определений и положений теории численного решения нелинейных уравнений. 2.Изучение основных методов численного решения нелинейных уравнений. 3.Разработка программ и решение на ЭВМ нелинейных уравнений. II. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ. Основные определения. Под решением нелинейного уравнения: f()=0 (2.) понимают нахождение корней этого уравнения, то есть определения значений, при которых выполняется условие: f( )= 0. Корень называется простым, если f ( ) 0. Корень называется кратным, если f ( ) = 0. Целое число m называется кратностью корня, если f ( k ) ( )= 0 для всех k=,2. m-, а f ( m ) ( ) 0. Решение уравнения (2.) проводится в два этапа: этапа локализации корней и этапа итерационного уточнения корней. На этапе локализации выделяется отрезок [a,b], внутри которого находится только один корень. На этапе итерационного уточнения корней задается точность вычислений ε и используется итерационный процесс (итерационная формула), в результате которого вычисляются значения последовательности: 0. n. При выполнении условия n ε итерационный процесс заканчивается. Если в итерационной формуле для вычисления приближения n используется только значение n-, то метод называют одношаговым, и k- шаговым, если используется k предыдущих приближений: n-k, n-k+. n-. Скорость сходимости итерационного процесса определяют с помощью следующего выражения, которое называется критерием сходимости итерационного процесса: p p =, > c> 0; n+ c n, (2.2) p>, c> 0. 3

4 где число p называют порядком сходимости метода. Если p=- сходимость линейная, p>- сверх линейная сходимость, p=2- сходимость квадратичная. Критерий окончания. Точное значение корня мы не знаем. Когда же закончить итерационный процесс, чтобы утверждать, что n + ε? Для каждого итерационного процесса существует свой критерий окончания в виде неравенства: n+ n δ(), ε при выполнении которого всегда имеет место неравенство: n + ε. Интервалом неопределенности корня называется интервал [

ε ], в котором любое значение может являться корнем уравнения. Появление такого интервала связано с погрешностью вычислений. Величина

ε определяется из условия:

y ε= f ( ), (2.3) где y- абсолютная предельная погрешность при вычислении значения функции y=f(). Так как значение

ε определяет абсолютную предельную погрешность вычисления значения корня = ±

ε (результата), которая возникла из-за погрешности вычисления значений функции y(.входных данных для задачи поиска корня), то величина ν = = y f ( ) называется абсолютным числом обусловленности задачи нахождения корня. 2. Методы решения нелинейных уравнений. Приведем основные методы решения нелинейных уравнений: а) метод бисекции. Выбирается отрезок [a,b], на концах которого функция имеет разные знаки, следовательно, корень находится внутри этого отрезка. Этот отрезок делится пополам и вновь выбирается отрезок, на концах которого функция имеет разные знаки и т.д. Таким образом, после n итераций имеем отрезок локализации [a n,b n ] длина которого в 2 n раз меньше первоначального отрезка [a,b]. Полагая n =(b n +a n )/2 имеем: bn an b a = < n ε. 2 n + 2 Данный метод обладает невысокой скоростью сходимости, но не требует чтобы функция была непрерывной. Однако этот метод нельзя использовать для поиска кратных корней. б) метод простой. Уравнение f()=0 преобразуют к виду удобному для организации : =ϕ(), при этом функция ϕ() 4

5 называется итерационной функцией. На отрезке локализации [a,b] выбирается начальное приближение = 0 и вычисляется =ϕ( 0 ). Продолжая этот процесс имеем: n+ = ϕ( n). Если существует lim =, то получаем равенство: =ϕ( ), где — n n корень. Метод сходится при ϕ ( ) <, [ a, b], а при ϕ ( ) >, [ a, b] — расходится. Критерий окончания: q ( n+ n) < ε, q q = ϕ ( ). (2.4) в) модифицированный метод простой. Итерационная функция имеет вид f () ϕ () = λ. f () Итерационная формула модифицированного метода простой и критерий окончания записываются следующим образом: f ( n ) n+ = λ, f ( ) (2.5) n+ n < ε. n г) метод касательных (метод Ньютона). Выбирается точка 0 [a,b] и в ней проводится касательная к графику функции y=f() и за новое приближение принимается точка, в которой касательная пересекает ось OX и т.д. В итоге получаем итерационную формулу Ньютона: f ( n ) n+ = n f ( n ). (2.6) Необходимым и достаточным условием сходимости метода Ньютона на отрезке локализации [a,b] являются: f () 0, — (необходимое условие); (2.7) f () 0 — (достаточное условие); т.е. знако постоянство первой и второй производной на отрезке локализации. д) метод хорд (модификация метода Ньютона). На отрезке [a,b] производную касательную в формуле (2.6) заменяют приближенным равенством: fb ( ) f ( n ) f ( n ), b n т.е. хордой. В итоге получаем: 5

6 b n n+ = n f ( n ). (2.8) fb ( ) f ( n ) е) метод секущих (модификация метода Ньютона). Если теперь точку b в формуле (2.8) заменить на точку n-, то получим формулу метода секущих: n n n+ = n f ( n ). (2.9) f ( n ) f ( n) Метод секущих является двух этапным. Все методы Ньютона (касательных, хорд и секущих) имеют квадратичную сходимость. Критерий окончания методов Ньютона: n+ n < ε, (2.0) III. ЗАДАНИЕ. Численно решить нелинейное уравнение из таблицы заданий для указанного в ней метода решения и указанной точности. 2. Оценить интервал неопределенности поиска корня, считая, что погрешность округления

Читайте так же:
Знак модуля в excel

0-0 и сравнить его с задаваемой точностью решения. 3. Проверить сходимость указанного метода на отрезке локализации. 4. Для указанного численного метода записать все соотношения, которые необходимы для разработки алгоритма программы. 5. Написать программу и рассчитать на ЭВМ значение корня указанного уравнения. 6. Разработать программу для решения данного уравнения методом бисекции. Рассчитать на ЭВМ значение корня. Сравнить результаты двух методов. IV. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ Задание. Решить методами секущих и модифицированным методом простой нелинейное уравнение: e -3-cos()=0, с точностью ε=0-4. Предельная абсолютная погрешность вычислений значений функции y=e — 3-cos() равна Проводим этап локализации. Так как cos( ), то при >2 имеем f()>0, а при =0 имеем f()<0. Следовательно, корень находится на отрезке [0,2]. 6

7 2. Оцениваем интервал неопределенности

ε на отрезке [0,2]. Согласно (2.3) имеем:

ε 0 0. [,] 02 Так как интервал неопределенности

ε 0 0 меньше погрешности поиска корня ε=0-4, то мы можем найти этот корень с заданной точностью. 3. Для приближенного решения уравнения используем формулу секущих (2.9): n n n+ = n f( n ), (4.2) f( n ) f( n) где f()=e -3-cos(). Проверяем условия сходимости (2.7): f ( ) = e + sin > 0, [ 02, ]; f ( ) = e + cos > 0, [ 02, ]. Так как необходимое и достаточное условия сходимости методов Ньютона выполнены на всем отрезке локализации, то для решения уравнения можем использовать метод секущих. 4. Выбираем начальные значения 0 =0., =0.3 и производим вычисления по итерационной формуле (4.2). Итерационный процесс завершаем при выполнении условия окончания для методов Ньютона (2.0): n+ n < ε. 5. Решаем ту же задачу модифицированным методом простой. Так же как и в методе секущих вначале задаем начальное приближение 0 =0., =0.3, а далее используем формулы (2.5) f ( n ) n+ = λ, f ( ) n+ n < ε. n 6. Пример текста программ на Mathcad и на Delphy (в консольном режиме) для нахождения корня уравнения методом секущих и модифицированным методом простой : 7

8 Поиск корня уравнения методом секущих f( ) := e 3 cos( ) ε := a := 0 b := := 0. := 0.3 f( ) ( ) := k Rf, a, b, 0,, ε while ( 0 > ε) ( 0 ) f( ) f( 0) f( ) 0 k k+ y 0 k y y ( ) Rf, a, b, 0,, ε = y 0 — количество итераций y — значение корня root( f ( ),, a, b) = Проверка встроенной программой MATHCAD 8

9 Поиск корня уравнения модифицированным методом простой f( ) := e 3 cos( ) f( ) := λ := 0.9 ff ( ) λ f( ) := f( ) a := 0 b := 2 0 := 0. ε := 0 9 Rff (, a, b, 0, e) := k while ( 0 > ε) Rff (, a, b, 0, e) = ff ( 0) 0 k k+ y 0 k y y d d f( ) ep( ) + sin( ) f( ) Задаем точку, чтобы использовать оператор while y 0 — количество итераций y — значение корня root( f ( ),, a, b) = Проверка встроенной программой MATHCAD program lab7; <Решение линейных уравнений методом секущих> < 0, - нулевое и первое приближения значения корня> < - новое приближение корня>var a,b,0,,e, of real; var i: integer; function f(y : real) : real; <функция для заданного нелинейного уравнения>9

10 end. begin f:=ep(y)-3-cos(y); end; begin writeln( Введите отрезок локализации a,b ); readln (a,b); writeln( Введите задаваемую точность e ); readln (e); writeln( Введите нулевое 0 и первое приближения ); readln (0,); i:=0; while abs(-0)>=e do begin :=-((0-)*f()/(f(0)-f()); if >=b then :=b; if <=a then :=a; 0:=; :=; i:=i+; end; writeln( Решение нелинейного уравнения методом секущих ); writeln( корень =,, точность e=,e, число итераций i=,i); 6. Заполняем таблицу: Метод Корень Точность Число итераций секущих, итераций, Название лабораторной работы. 2. Индивидуальное задание. 3. Теоретическая часть. 4. Текст программы. 5. Результаты расчета. V. СОДЕРЖАНИЕ ОТЧЕТА 0

11 Пункты -4, а также таблица должны, быть оформлены до начала лабораторной работы. VI.КОНТРОЛЬНЫЕ ВОПРОСЫ. Что называется корнем уравнения? 2. Определение простого и кратного корня. 3. Основные этапы поиска корня. 4. Определение скорости и порядка сходимости численного метода поиска корня. 5. Определение интервала неопределенности корня. 6. Число обусловленности задачи поиска корня нелинейного уравнения. 7. Метод бисекции. 8. Метод простой операции. 9. Методы Ньютона и его модификации. 0. Критерий окончания метода простой для задачи поиска корня.. Метод Ньютона для решения системы нелинейных уравнений. 2. Определение якобиана. 3. Критерий окончания методов Ньютона. VII. ТАБЛИЦА ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ f() Метод Точность 2 ln( ) / ( + ) хорд ln(ln( )) 2 касательных / e простой ( / ) секущих ln( ) хорд e касательных sin( ) 6+ простой cos( ) 0 секущих ln ( / ) хорд 0-4

12 f() Метод Точность 0 arctg( ) ln( ) простой ln( + ) / ( ) cos( ) касательных e 3 cos( ) секущих e arctg() хорд arctg( / ) касательных /( ) простой касательных sin () + простой cos ( ) + секущих ln( + ) (/( + ) ) хорд arctg() ln(( + ) + ) простой ln( + ) /( + ) cos( ) касательных e cos () секущих e 3 arctg( + 2) хорд arctg(/ ) касательных /( + + ) простой 0-6 2

Метод хорд и касательных в excel

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

Прежде всего рассмотрим метод хорд. Пусть искомый корень уравнения

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

При этом возможны четыре случая: 1°. не убывает и положительна на не возрастает и отрицательна на не возрастает и положительна на не убывает и отрицательна на

Читайте так же:
Макрос объединение файлов excel в один

Ради определенности подробно рассмотрим случай 1°.

Рассмотрим вместо уравнения (11.6) уравнение вида

Легко видеть, что изолированные на сегменте корни уравнений (11.6) и (11.7) совпадают, и поэтому на сегменте эти уравнения эквивалентны. Для решения уравнения применим к этому уравнению метод итераций, выбрав за нулевое приближение точку а. Как обычно, определим последовательность по рекуррентной формуле

Докажем, что последовательность сходится к искомому корню с. Для этого, в силу утверждения 1 из достаточно доказать, что все лежат на сегменте и что последовательность сходится.

Применяя метод индукции, докажем, что все лежат на сегменте точнее, на сегменте , где с — искомый корень. Так как лежит на сегменте , то для проведения индукции достаточно, предположив, что лежит на указанном сегменте, доказать, что также лежит на этом сегменте. Поскольку

то, учитывая, что будем иметь

Применяя к выражениям в квадратных скобках формулу Лагранжа, получим

В силу неубывания и положительности производной можем записать Отсюда, так как получим

Таким образом, из равенства (11.9) найдем или т. е. индукция проведена.

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

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

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

Как уже указано выше, кроме рассмотренного выше случая 1° возможны еще следующие три случая: 2° производная не зозрастает и отрицательна на сегменте производная не возрастает и положительна на сегменте производная не убывает и отрицательна на сегменте Эти случаи изображены соответственно на рис. 11.5, 11.6, 11.7.

В случае 2″ уравнение (11.6), так же как и выше, заменяется уравнением (11.7) и в качестве нулевого приближения берется точка (при этом последовательность также оказывается неубывающей). В случаях 3° и 4° уравнение (11.6) заменяется не уравнением (11.7), а следующим уравнением

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

Приведенная выше геометрическая иллюстрация является источником наименования метода хорд.

Перейдем теперь к изложению метода касательных или метода Ньютона.

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

Ради определенности рассмотрим подробно случай 1°, т. е. предположим, что производная не убывает и положительна на сегменте

Заменим уравнение (11.6) эквивалентным ему на сегменте уравнением

и будем решать последнее уравнение методом итераций, приняв за нулевое приближение точку и определив последовательность рекуррентной формулой

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

Применяя метод индукции, докажем, что все лежат на сегменте точнее, на сегменте где с — искомый корень. Так как лежит на сегменте то для проведения

индукции достаточно, предположив, что лежит на сегменте доказать, что и также лежит на этом сегменте. Если , то и из формулы (11.11) следует, что , т. е. индукция проведена. Пусть теперь . Тогда из формулы (11.11), учитывая, что , получим

Применяя к выражению, стоящему в числителе последней дроби, формулу Лагранжа, найдем

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

Таким образом, индукция проведена. Из положительности производной следует возрастание функции а поэтому из неравенства следует, что Таким образом, Отсюда в силу формулы т. е. последовательность не возрастает. Так как эта последовательность, кроме того, ограничена снизу числом с, то по теореме 3.15 она сходится. В силу утверждения 1 из п. 2 пределом ее является искомый корень с.

Дадим геометрическую иллюстрацию рассмотренного нами случай 1°. Из формулы (11.11) вытекает, что является абсциссой точки пересечения с осью касательной к графику функции в точке (на рис. 11.8 изображены точки Приведенная геометрическая иллюстрация является источником наименования метода касательных. Предлагаем читателю самостоятельно разобрать метод касательных для случаев 2°, 3°, 4°, указанных при изложении метода хорд.

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

где — минимальное значение на сегменте Формула (11.12) позволяет оценить отклонение от точного значения корня с через значение модуля заданной функции в точке

Замечание 2. На практике часто используют комбинированный метод, заключающийся в поочередном применении метода хорд и метода касательных. Ради определенности остановимся на подробно рассмотренном выше случае 1°, т. е. предположим, что не убывает и положительна на сегменте (рис. 11.9). Определим по методу касательных, взяв за нулевое приближение точку После этого определим применяя метод хорд, но не к сегменту а к сегменту

Далее, определим по методу касательных, исходя из уже найденного по. методу хорд, применяя его к сегменту Указанный процесс иллюстрируется на рис. 11.9.

Читайте так же:
Как восстановить историю в хроме после удаления

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

Метод касательных. Скорость сходимости. Критерий окончания

Метод касательных (метод Ньютона).Выбирается точка xÎ[a,b] и в ней проводится касательная к графику функции y=f(x) и за новое приближение x1 принимается точка, в которой касательная пересекает ось OX и т.д. В итоге получаем итерационную формулу Ньютона:

(2.6)

Необходимым и достаточным условием сходимости метода Ньютона на отрезке локализации xÎ[a,b] являются:

f¢(x)¹0, — (необходимое условие); (2.7)

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

Критерий окончанияметодов Ньютона:

Все методы Ньютона (касательных, хорд и секущих) имеют квадратичную сходимость.

Обусловленность задачи численного интегрирования

Относительное число обусловленности задачи численного интегрирования

Экзаменационный билет № 24

Требования к вычислительным программам

Требования к программным реализациям алгоритмов

1. Надежность(без ошибок)

Модификации метода Ньютона для решения нелинейных уравнений

Метод хорд (модификация метода Ньютона).На отрезке [a,b] производную касательную в формуле (2.6) заменяют приближенным равенством:

т.е. хордой. В итоге получаем:

(2.8)

Метод секущих (модификация метода Ньютона). Если теперь точку b в формуле (2.8) заменить на точку xn-1, то получим формулу метода секущих:

(2.9)

Метод секущих является двух этапным.

Все методы Ньютона (касательных, хорд и секущих) имеют квадратичную сходимость.

Критерий окончанияметодов Ньютона:

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

Экзаменационный билет № 25

Метод ячеек

Пусть требуется вычислить двукратный интеграл в области G(a£x£b, c£y£d):

С помощью узлов xi (i=0,1. n) и yj (j=0,1. m) и прямых, проходящих через эти узлы: x=xi и y=yj, разобьем область G на (n×m) прямоугольных ячеек, имеющих площадь:

Выбираем в этой ячейке центральную точку:

Будем считать, что интеграл для каждой ячейке приближенно равен:

(2.12)

Суммируя по всем ячейкам имеем:

(2.13)

при этом погрешность, когда все ячейки имеют одинаковую площадь будет равна

; (2.14)

где S — площадь области G, m и n — количество узлов по координатам x,y; , — максимальное значение вторых частных производных по соответствующим координатам.

Системы нелинейных уравнений. Метод простой итерации. Метод Ньютона

Версия

Метод простой итерации.Уравнение f(x)=0 преобразуют к виду удобному для организации итерации: x=j(x), при этом функция j(x) называется итерационной функцией. На отрезке локализации [a,b] выбирается начальное приближение x=x и вычисляется x1=j(x). Продолжая этот процесс имеем:

.

Если существует , то получаем равенство: где — корень. Метод сходится при , а при — расходится.

Метод касательных (метод Ньютона).Выбирается точка xÎ[a,b] и в ней проводится касательная к графику функции y=f(x) и за новое приближение x1 принимается точка, в которой касательная пересекает ось OX и т.д. В итоге получаем итерационную формулу Ньютона:

(2.6)

Необходимым и достаточным условием сходимости метода Ньютона на отрезке локализации xÎ[a,b] являются:

f¢(x)¹0, — (необходимое условие); (2.7)

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

Версия

Пусть имеется следующая система нелинейных уравнений:

(6.5)

Как уже отмечалось выше, для одной переменной метод Ньютона использует замену искомого уравнения уравнением прямой или, как еще говорят, производит линеаризацию исходного уравнения. Пусть имеется k — ое приближение: . Разложим левые части системы уравнений в ряд Тейлора и учтем только линейные члены:

(6.6)

где , i=1,2. n; а частные производные вычисляются в точке k-го приближения: x1=x1 ( k ) , x2=x2 ( k ) . xn=xn ( k ) .

Заменим в исходной системе нелинейные функции fi(x1,x2. xn) на правые части этих приближенных равенств, которые являются линейными функциями относительно переменных xi, i=1,2. n. В итоге получим следующую систему линейных уравнений относительно переменных xi, i=1,2. n:

(6.7)

Из этой системы можно определить значения xi, i=1,2. n и вычислить значения k+1-приближения: . Данная система уравнений представляют собой метод Ньютона для системы нелинейных уравнений.

Определитель этой системы называетсяякобианом.

. (6.8)

Для существования решения якобиан должен быть отличен от нуля для каждого шага итерации.

Критерий окончания. Итерационный процесс продолжается до тех пор, пока не выполнятся условия: , для всех i=1,2. n.

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

Этот метод применяется при решении уравнений вида f(x) = 0, если корень уравнения отделён, т.е. и выполняются условия:

1) (функция f(x) принимает значения разных знаков на концах отрезка.

2) производная сохраняет знак на отрезке [a; b], т.е. функция f(x) либо возрастает, либо убывает на отрезке [a; b].

Первое приближение корня находится по формуле:

Для следующего приближения из отрезков [a; х 1 ] и [х 1 ; b] выбирается тот, на концах которого функция f(x) имеет значения разных знаков.

Если , то второе приближение вычисляется по формуле:

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

Читайте так же:
Можно ли изменить емайл
Метод касательных (Ньютона).

Этот метод применяется, если уравнение f(x) = 0 имеет корень , и выполняются условия:

1) (функция принимает значения разных знаков на концах отрезка [a; b];

2) производные сохраняют знак на отрезке [a; b], т.е. функция f(x) либо возрастает, либо убывает на отрезке [a; b], сохраняя при этом направление выпуклости.

На отрезке [a; b] выбирается такое число х 0 , при котором f(x 0 ) имеет тот же знак, что и , т. е. выполняется условие . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой на отрезке [a; b], пересекает ось OX. За точку x 0 сначала удобно выбирать один из концов отрезка.

Первое приближение корня определяется по формуле: .

Второе приближение корня определяется по формуле: .

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

Достоинства метода: простота, быстрота сходимости.

Недостатки метода: вычисление производной и трудность выбора начального положения.

Комбинированный метод хорд и касательных.

Если выполняются условия:

2) и сохраняют знак на отрезке [a; b],

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

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

1. Вычислить значения функции и .

2. Проверить выполнение условия . Если условие не выполняется, то неправильно выбран отрезок [a; b].

3. Найти производные .

4. Проверить постоянство знака производных на отрезке [a; b]. Если нет постоянства знака, то неверно выбран отрезок [a; b].

5. Для метода касательных выбирается за х 0 тот из концов отрезка [a; b], в котором выполняется условие , т.е. и одного знака.

6. Приближения корней находятся:

а) по методу касательных: ,

б) по методу хорд: .

7. Вычисляется первое приближение корня: .

8. Проверяется выполнение условия: , где — заданная точность.

Если условие не выполняется, то нужно продолжить применение метода по схеме 1 – 8.

В этом случае отрезок изоляции корня сужается и имеет вид . Приближённые значения корня находятся по формулам:

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

В простейших случаях используют метод простых итераций, вычисляя последовательно значения функции у = f(x), изменяя значения х, чтобы у→ 0 и его модификацию – «метод вилки», изменяя величину х так, чтобы если f(x 1 ) > 0, то f(x 2 ) 1 ; х 2 ].

1.2.2. Интерполяция функций.

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

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

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

На практике чаще всего применяют интерполяцию многочленами. Это связано прежде всего с тем, что многочлены легко вычислять, легко аналитически находить их производные.

Линейная интерполяция – интерполяция алгебраическим двучленом Р 1 (x) = ax + b функции f(x), заданной в двух точках x 0 и x 1 отрезка [a, b].

В случае, если заданы значения в нескольких точках, функция заменяется кусочно-линейной функцией.

Интерполяционная формула Ньютона применяется, если узлы интерполяции равноотстоящие и упорядочены по величине, так что x i + 1 − x i = h = const, то есть x i = x 0 + ih. Тогда интерполяционный многочлен можно записать в форме Ньютона.

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

Короткая форма интерполяционной формулы Ньютона

В случае равноудаленных центров интерполяции, находящихся на единичном расстоянии друг от друга, справедлива формула:

где – обобщенные на область действительных чисел биномиальные коэффициенты.

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

а выражения вида Δ k y i – конечные разности.

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

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

Для n + 1 пар чисел , где все x i различны, существует единственный многочлен L(x) степени не более n, для которого L(x i ) = y i . В простейшем случае (n = 1) – это линейный многочлен, график которого – прямая, проходящая через две заданные точки.

Лагранж предложил способ вычисления таких многочленов:

где базисные полиномы определяются по формуле:

l j (x) обладают следующими свойствами:

а) являются многочленами степени n; б) l j (x j ) = 1; в) l j (x i ) = 0 при .

Отсюда следует, что L(x), как линейная комбинация l j (x), может иметь степень не больше n, и L(x j ) = y j .

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector