Помощь по Теле2, тарифы, вопросы

Перечислим недостатки метода Ньютона, на устранение которых направлены различные его модификации:

трудность задания начального приближения, от которого метод сходится;

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

необходимость решения на каждой итерации системы линейных алгебраических уравнений;

требование невырожденности матрицы Якоби.

Рассмотрим модификации метода Ньютона, которые в той или иной мере устраняют перечисленные недостатки.

Метод Ньютона с кусочно-постоянной матрицей.

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

в котором, например (матрица Якоби лишь при нарушении этого условия вычисляется заново).

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

Метод Ньютона-Рафсона.

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

где - параметр, значение которого на k -й итерации выбирается из условия

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

Методы продолжения по параметру.

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

Пусть при решении системы

используется начальное приближение. Заменим исходное уравнение уравнением с параметром

которое при имеет решение, а при совпадает с решением исходной задачи, т. е.

В качестве можно выбрать функции

Разобьем отрезок точками на интервалов. Получим искомую последовательность систем:

Метод Ньютона для плохо обусловленных задач.

Если матрица Якоби плохо обусловлена, погрешность решения линейной системы

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

случае плохо обусловленных матриц при вычислении вектора поправок привлекают систему

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

Опыт показывает, что при исследовании неквадратичных функ­ций метод Ньютона не отличается высокой надежностью. В самом деле, если точка х (0) находится на значительном расстоянии от точки х*, шаг по методу Ньютона часто оказывается чрезмерно большим, что может привести к отсутствию сходимости. Метод можно довольно просто модифицировать, с тем чтобы обеспечить уменьшение целевой функции от итерации к итерации и осуществлять поиск вдоль прямой, как в методе Коши. Последовательность итераций строится в соответствии с формулой

x = x – α f (x ) f(x ). (3.56)

Выбор α осуществляется таким образом, чтобы

f (x ) → min;

это гарантирует выполнение неравенства

f (x ) ≤ f (x ).

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

Метод Марквардта

Рассматриваемый метод является комбинацией методов Коши и Ньютона, в которой удачно сочетаются положительные свойства обоих методов. Вместе с тем при использовании метода Марквардта требуется информация о значениях вторых производных целевой функции. Выше было отмечено, что градиент указывает направление наибольшего локального увеличения функции, а движение в направлении, противоположном градиенту, из точки х (0) , расположенной на значительном расстоянии от точки минимума х*, обыч­но приводит к существенному уменьшению целевой функции. С другой стороны, направления эффективного поиска в окрестности точки минимума определяются по методу Ньютона. Простая идея объеди­нения методов Коши и Ньютона была положена в основу алгоритма, разработанного Марквардтом в 1963 г. В соответствии с этим методом направление поиска определяется равенством

s (x (k)) = – [Н (k) + λ (k) I ] -1 f (x (k)). (3.57)

При этом в формуле (3.42) следует положить α (k) = +1, поскольку параметр λпозволяет не только изменять направление поиска, но и регулировать длину шага. Символом I здесь обозначена единичная матрица, т. е. матрица, все элементы которой равны нулю, за исклю­чением диагональных элементов, равных +1. На начальной стадии поиска параметру λ (0) приписывается большое значение (например, 10 4), так что

[Н (0) + λ (0) I ] -1 = [λ (0) I ] -1 = I. (3.58)

Таким образом, большим значениям λ (0) соответствует направление поиска s(x (0)) → f (x (0)).Из формулы (3.57) можно заключить, что при уменьшении λ до нуля s(x) изменяется от направления, противоположного градиенту, до направления, определяемого по методу Ньютона. Если после первого шага получена точка с меньшим значением целевой функции (т.е. f (х (1)) < f (x (0))), следует выбрать λ (1) < λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β > 1, и вновь реализовать предыдущий шаг. Ниже представлены шаги алгоритма.

Алгоритм Марквардта

Шаг 1.Задать х (0) - начальное приближение к х*; М - максимальное (допустимое) количество итераций; ε- параметр сходимости.

Шаг 2.Положить k = 0, λ (0) = 10 4 .

Шаг 3.Вычислить компоненты f (x (k)).

Шаг 4.Выполняется ли неравенство

|| f (x (k))|| < ε?

Да: перейти к шагу 11.

Шаг 5.Выполняется ли неравенство k ≥ M ?

Да: перейти к шагу 11.

Нет: перейти к следующему шагу.

Шаг 6.Вычислить s (x (k)) = – [Н (k) + λ (k) I ] -1 f (x (k)).

Шаг 7.Положить x = x s (x ).

Шаг 8.Выполняется ли неравенство f (x ) < f (x )?

Да: перейти к шагу 9.

Нет: перейти к шагу 10.

Шаг 9.Положить λ (k +1) = ½ λ (k) и k = k+ 1. Перейти к шагу 3.

Шаг 10.Положить λ (k) = 2λ (k) . Перейти к шагу 6.

Шаг 11.Печать результатов и останов.

Метод Марквардта характеризуется относительной простотой, свойством убывания целевой функции при переходе от итерации к итерации, высокой скоростью сходимости в окрестности точки минимума х* , а также отсутствием процедуры поиска вдоль прямой. Главный недостаток метода заключается в необходимости вычисления Н (k) и последующего решения системы линейных уравнений, соответствующей (3.57). Этот метод широко используется при решении задач, в которых f(x) записывается в виде суммы квадратов 1) , т.е.

f (x) = f (x) + f (x) +…+ f (x) . (3.59)

Именно такая задача рассматривалась Марквардтом. Пауэлл и Бард на основе вычислительных экспериментов показали, что метод Марквардта отличается высокой эффективностью при решении задач такого типа.

Метод Ньютона и метод секущих

Метод Ньютона в случае простого вещественного корня имеет вид

x k+1 = x k - ――― , k = 1,2,…. (8.6)

f ′(x k)

в случае корня кратности r

x k +1 - x k

f ′(x k)―――― + f(x k) = 0 .

Оценка погрешности следующая:

|х k - x * | £ q |x 0 - x * |, k = 1,2,….

M p+1 |x 0 - x * |

q = ――――― < 1.

m p p(p + 1)

Можно пользоваться оценкой погрешности как в методе простой итерации, учитывая, что метод Ньютона

sx) = x – p ――

x k+1 = x k - ――― , k = 0, 1, ….

f′(x 0)

применяют в том случае, когда хотят избежать многократного вычисления производной ¦¢(x k).

В методе Ньютона требуется вычислять производную функции, что не всегда удобно. Можно заменить производную первой разделённой разностью, найденной по двум последним итерациям. Тогда вместо метода Ньютона (8.6) получим метод секущих

(x k – x k -1)f(x k)

x k+1 = x k - ――――――

f(x k) – f(x k-1)

Для начала процесса требуется знать значения х 0 и х 1 .

ЗАДАНИЯ К ЛАБОРАТОРНОЙ РАБОТЕ.

1.Отделить вещественные корни аналитически или графически.

2.Уточнить корни делением отрезка пополам (если это возможно) с точностью до 0.1.

3.Уточнить корни заданным методом с заданной точностью.

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

4.Проверить результаты подстановкой найденных значений в уравнение.

ВАРИАНТЫ

1. Найти все корни уравнения

1000000 x 4 - 3000 x 3 + 1000002 x 2 - 3000 х + 2 = 0

с точностью 0.0001 методом а) Ньютона б) секущих.

2. Найти все корни уравнения

x 4 - 10001.01 x 3 -9800.01 x 2 - 999901 х + 10000 = 0

с точностью 0.001 а) методом Ньютона б) Модифицированным методом Ньютона.

3. Найти все корни уравнения

на отрезке с точностью 0.001 методом Ньютона.

4. Найти все корни уравнения

5. Найти корень уравнения

x 4 - 20 x 3 + 101 x 2 - 20 х + 1 = 0

на отрезке [-1,1] с точностью 0.0001 методом Ньютона с параметрами

заданной точности.

6. Найти корень уравнения

7. Найти все корни уравнения

x 5 - 3 x 2 + 1 = 0

методом парабол с точностью 0.0005.

8. Найти вещественные корни уравнения

9. Выяснить, к какому из корней 0, 1,-1 уравнения

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

10. Найти все корни уравнения

x 3 + 3 x 2 - 1 = 0

методом простой итерации с точностью 0. 0005.

11. Найти все корни уравнения

х 4 - 10000.01 x 3 +101 x 2 - 10000.01 х + 100 = 0

с точностью до 0.001 а) методом Ньютона б) модифицированным методом Ньютона.

12. Найти корень уравнения

arccos (x/2) = x 2

на отрезке а) методом Ньютона б) модифицированным методом Ньютона.

13. Найти все корни уравнения

x 4 – 0.015х 3 + 0.3х 2 + х – 1 = 0

14. Найти корень уравнения

х 3 – sin (2x) = 1

методом парабол с точностью 0.001.

15. Найти все корни уравнения

х 3 – 1777х 2 + 777 = 0

на отрезке [-1,1] методом парабол с точностью до 0.0001

16. Найти все корни уравнения

5555х 4 – 555х 3 – 55х 2 – 5х = 0

с точностью 0.00001 методом а) Ньютона б) секущих.

17. Найти корень уравнения

arctg (7x) = 0.2

на отрезке [-1,1] а) методом Ньютона б) модифицированным методом Ньютона.

18 . Найти корень уравнения

sin (x 4) = 1 – 2x

методом парабол с точностью 0.0001.

19 . Найти корень уравнения

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

20. Найти все корни уравнения

x 3 – 45x 2 + 43 = 0

на отрезке [-2,1] а) модифицированным методом Ньютона б) методом секущих.

21 . Найти корень уравнения

arcsin (x) + e x = 2

методом простой итерации с точностью до 0.001 сделав предварительную оценку погрешности.

22. Найти все корни уравнения

54x 4 + x 2 – 0.0000001 =0

с точностью 0.00001 методом а) Ньютона б) секущих.

23. Найти все корни уравнения

tg (x/3) – x 3 = 0

методом парабол с точностью 0.001.

24. Найти все корни уравнения

12x 4 + 11x 3 –10x 2 –999 = 0

на отрезке [-3.5,3] с точностью 0.0001 методом Ньютона с параметрами

р=1 и р=2. Сравнить количества итераций необходимые для достижения

заданной точности.

25 . Найти корень уравнения

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

ОТВЕТЫ:1) 0,0100; 0,0200 2) 0,688; 10000 3) 0,107; 0,155; 0,361 4) –1,32; 0; 1,32 5) 0,0917; 0,1125 6) 0 7) –0,5611; 0,5992; 1,348 8) –0,637; 1,41 9) –1; 0; 1 10) -2,879; -0,6527; 0,5321 11) 0,231; 10000 12) 1,01817183 13) –1,1468; 0,66935; 1 14) 1,191 15) -0,6611; 0,6614 16) –0,09811;0,19695 17) 0,028959 18) 0,4746 19) 0,987 20) –0,9672; 0,9884; 44,98 21) 0,4369 22) +/- 0,0003 23) +/- 0,581; 0 24) -3,36; 2,875 25) 1,2784.

Модифицированный метод Ньютона основан на методе Ньютона. Если производная изменяется незначительно на отрезке, то можно предположить.

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

N=0,1,2... (1.16)

Геометрически этот способ означает, что мы заменяем касательные в точках на прямые, параллельные касательной к кривой в фиксированной точке.

Данный метод позволяет отказаться от многократного вычисления производной в точках. Модифицированный метод Ньютона используют для решения уравнений, в которых вычисление производной является трудоемким и относительно долговременным. В других случаях лучше применять стандартный метод Ньютона.

Ограничения на функцию и начальное приближение у модифицированного и стандартного методов Ньютона совпадают. Алгоритм обоих методов практически один и тот же.

Модифицированный метод Ньютона обладает линейной сходимостью

Метод гарантирует отсутствие деления на ноль, если .

Пример . Уравнение.

Применяют метод Ньютона с параметром, т.к. корень имеет кратностьp=2. Возьмем начальное приближениеи получаем. Корень найден.

Пример . Уравнение.

Корень изолирован на отрезке . Погрешность Eps равна 0.000001

Метод Ньютона сходится за 5 итераций, модифицированный метод Ньютона за 19 итераций, метод половинного деления за 22 итерации. Сходимость метода итераций зависит от выбора параметра. При сходимость достигается за 24 итерации,сходимость за 11 итераций,сходимость за 6 итераций,сходимость за 25 итераций.

Метод секущих

Метод секущих получается из метода Ньютона заменой разделенной разностью

вычисленной по известным приближениям и.

Соответственно получается следующая формула метода секущих

. (1.18)

Данный метод является двухшаговым (т.к. надо знать два предыдущих шага для выполнения нового шага). Этим он отличается от всех ранее приведенных методов - одношаговых.

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

Интегрирование функций Постановка задачи

Пусть на отрезке задана непрерывная функция. Построим разбиение отрезка точкамина частичные отрезки:

Длина отрезков равна .

Назовем интегральной сумму

Определенным интегралом функции на отрезкеназывается

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

Как можно вычислить интеграл на практике? Для этого обычно используют формулу Ньютона - Лейбница:

где P (x ) - первообразная функцииF (x ) , т.е..

Формула Ньютона - Лейбница играет большую роль в математическом анализе. Но можно ли ее применять при решении задачи на компьютере? Можно, но не всегда (т.к. первообразная не всегда существует).

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

Это позволяет сделать вывод, что формула Ньютона - Лейбница не дает общего, универсального метода нахождения определенного интеграла от произвольной функции и ее не рекомендуется применять в профессиональных программах для ЭВМ. Формулу Ньютона - Лейбница применяют только для проверки новых разработанных программ, в которых были реализованы другие методы приближенного интегрирования функций.

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

Соответствующие формулы называют формулами численного интегрирования или квадратурными формулами 5 .

Шаг разбиения в этом случае считают по формуле .