Численные методы в Excel. Реализация численных методов решения нелинейных уравнений средствами приложения MS Excel

Пусть найдено приближенное значение корня уравнения f (x ) = 0, обозначим его x n . Расчетная формула метода Ньютона для определения очередного приближения x n +1 может быть получена двумя способами.

Первый способ выражает геометрический смысл метода Ньютона и состоит в том, что вместо точки пересечения графика функции y = f (x ) с осью OX , мы ищем точку пересечения с осью OX касательной, проведенной к графику функции в точке (x n , f (x n )) как показано на рис. 2.6. Уравнение касательной имеет вид .

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

В точке пересечения касательной с осью OX переменная y = 0. Приравнивая y нулю, выразим x и получим формулу метода касательных :

(2.6)

Второй способ. Разложим функцию f (x ) в ряд Тейлора в окрестности точки x = x n :

Ограничимся линейными относительно (x – x n ) слагаемыми, приравняем нулю f (x ) и, выразив из полученного уравнения неизвестное x и обозначив его через x n +1 , мы получим формулу (2.6).

Приведем достаточные условия сходимости метода Ньютона.

Теорема 2.3. Пусть на отрезке выполняются условия:

1) функция и ее производные и непрерывны;

2) производные и отличны от нуля и сохраняют определенные постоянные знаки;

3) (функция меняет знак на отрезке).

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

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

Рис. 2.8. Достаточные условия сходимости метода Ньютона

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

Пример 2.7. Уточнить до 0,000001 методом Ньютона корень уравнения
sin 5x + x 2 – 1 = 0. За начальное значение принять x 0 = – 0,7.

Решение. Найдем производную .

В программе Excel введем расчетные формулы:

1) Введем формулы и обозначения в ячейках диапазона A 1:D 3 и скопируем вниз маркером заполнения ячейки с формулами: B 3 - до B 5,
C 2 - до C 5, D 2 - до D 5;

Таблица 2.9

	A	B	C	D
	k	x	f(x)	f"(x)
		–0,7	=SIN(5*B2)+B2^2–1	=5*COS(5*B2)+2*B2
		=B2–C2/D2

Результаты расчетов приведены в таблице 2.10. Получено значение корня – 0,726631609 ≈ – 0,726632 с погрешностью 0,000001.

Таблица 2.10

	A	B	C	D	A
	k	x	f(x)	f"(x)
		-0,7	-0,159216772	-6,082283436
		-0,726177138	-0,002664771	-5,865681044	0,026177138
		-0,726631437	-1,00787E-06	-5,861240228	0,000454299
		-0,726631609	-1,45328E-13	-5,861238543	1,71955E-07

Создадим функции в программе Excel для решения уравнения из примера 2.7 методом Ньютона.

" В отличие от метода хорд, в методе касательных вместо хорды на каждом шаге проводится касательная к кривой y=F(x) при x=x n и ищется точка пересечения касательной с осью абсцисс:

Формула для (n+1) приближения имеет вид:

Если F(a)*F"(a)>0 , x 0 =a , в противном случае x 0 =b .

Итерационный процесс продолжается до тех пор, пока не будет обнаружено, что:

Пример:

Пусть дана задача следующего характера: Уточнить корни уравнения cos(2x)+x-5=0 методом касательных с точностью до 0,00001.

Изначально необходимо определиться с тем, чему равно x0: либо a, либо b. Для этого необходимо выполнить следующие действия:

Найти производную первого порядка от функции f(x)=cos(2x)+x-5. Она будет выглядеть следующим образом: f1(x)=-2sin(2x)+1.

Найти производную второго порядка от функции f(x)=cos(2x)+x-5. Она будет выглядеть следующим образом: f2(x)=-4cos(2x).

В итоге получается следующее:

Так как x0=b, то необходимо выполнить следующие действия:

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

В ячейку A6 ввести формулу =D5.

Выделить диапазон ячеек B5:E5 и методом протягивания заполнить диапазон ячеек B6:E6.

Выделить диапазон ячеек A6:E5 и методом протягивания заполнить диапазон нижерасположенных ячеек до получения в одной из ячеек столбца E результата (диапазон ячеек A6:E9).

В итоге получаем следующее:

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

Для того чтобы достичь наиболее точной погрешности, нужно одновременно использовать методы хорд и касательных. "По формуле хорд находят x n+1 , а по формуле касательных - z n+1 . Процесс нахождения приближенного корня прекращается, как только:

В качестве приближенного корня берут значение, равное (11) :"[2 ]

Пусть требуется уточнить корни уравнения cos(2x)+x-5=0 комбинированным методом с точностью до 0,00001.

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

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

Для формул хорд обозначить:

Переменная c будет играть роль a или b в зависимости от ситуации.

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

Для формулы касательных обозначить:

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

Найти производную первого порядка от функции f(x)=cos(2x)+x-5. Она будет выглядеть следующим образом: f1(x)=-2sin(2x)+1.

Найти производную второго порядка от функции f(x)=cos(2x)+x-5. Она будет выглядеть следующим образом: f2(x)=-4cos(2x).

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

В итоге получается следующее:

В ячейку G1 ввести e, а в G2 ввести число 0,00001.

В ячейку H1 ввести c, а в H2 ввести число 6, так как c=b (см. ячейку F2).

В ячейку I1 ввести f(c), а в I2 ввести формулу =COS(2*H2)+H2-5.

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

В ячейку A6 ввести формулу =E5.

В ячейку F6 ввести формулу =I5.

Выделить диапазон ячеек B5:E5 и маркером автозаполнения заполнить диапазон ячеек B6:E6.

Выделить диапазон ячеек G5:K5 и маркером автозаполнения заполнить диапазон ячеек G6:K6.

Выделить диапазон ячеек A6:K6 и методом протягивания заполнить все нижестоящие ячейки до получения ответа в одной из ячеек столбца K (диапазон ячеек A6:K9).

В итоге получаем следующее:

Ответ: Корень уравнения cos(2x)+x-5=0 равен 5,32976.

n Пример 2.3. Найти корни уравнения

x - tg(x)= 0. (2.18)

Первый этап решения (этап отделения корней ) был реализован в разделе 2.1 (пример 2.2). Искомый корень уравнения находится на отрезке x Î, что и видно на графике (рис. 2.9).

Рис.2.9. Этап отделения корней

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

Последовательность действий:

1. Подготовим таблицу, как показано на рис.2.10 и введем значения a , b , ε соответственно в ячейки В3, В4, В5.

2. Заполним первую строку таблицы:

D4=0 номер итерации;

Е4=В3, F4=B4, для вычисления f(a): G4=E4-TAN(E4),

Аналогично, в ячейки H4, I4, J4 введем формулы для вычисления соответственно f (b ), x n =(a+b )/2 и f (x n );

В ячейке К4 вычислим длину отрезка [a , b ]: K4=ABS(E4-F4).

3. D5=D4+1, для формирования номера итерации.

4. В ячейки E5, F5 введем формулы для формирования концов вложенных отрезков в соответствии с алгоритмом, изложенным в разделе 2.2.1:

E5=ЕСЛИ(J4*H4<0;I4;E4);

F5=ЕСЛИ(J4*H4>0;I4;F4).

5. Выделим ячейки G4:K4 и скопируем их вниз на одну строку .

6. Выделим ячейки D5:K5 и скопируем их вниз до конца таблицы.

Рис.2.10. Схема решения нелинейного уравнения методом бисекции

Деление отрезков продолжаем до тех пор, пока длина последнего не станет меньше заданного ε, т.е. до тех пор, пока не выполнится условие .

Чтобы сделать наглядным окончание итерационного процесса, воспользуемся Условным форматированием

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

Для этого выполним следующие действия:

Выделим ячейки последнего столбца (К) расчетной схемы (рис.2.10), где будет задаваться критерий окончания итерационного процесса;

Выполним команду

Главная\Стили\ Условное форматирование;

Рис.2.11. Окно условного форматирования

В появившемся окне (рис.2.11) выберем строку:

Правила выделения ячеек \ Меньше;

В левой части появившегося диалогового окна Меньше (рис.2.12) зададим значение, которое будем использовано в качестве критерия (в нашем примере это адрес ячейки B5, где находится значение ε ).

Рис.2.12. Диалоговое окно Меньше

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

В результате такого форматирования ячейки столбца К, значения которых меньше 0.1, тонированы, рис.2.10.

Таким образом, за приближенное значение корня уравнения x- tg(x)= 0 с точностью e=0.1принимается 3-я итерация, т.е. x * »4.46875 . Для e=0.01 - x * » 4.49609 (6-я итерация).

Решение нелинейных уравнений с использованием надстройки «Подбор параметра»

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

Найдем корни рассмотренного выше уравнения (2.18).

За нулевое приближение решения уравнения, как это видно из рис.2.13, можно принять х 0 =4 или х 0 =4,5.

Последовательность действий

1. Подготовим таблицу, как показано на рис.2.13. В ячейку А2 введем некоторое значение х 0 (например х 0 =4) из ОДЗ функции y=f(x). Это будет начальным приближением для итерационного процесса, реализуемого приложением Подбор параметра.

2. Ячейка В2 является изменяемой ячейкой в процессе работы надстройки. Введем в нее это значение х 0 , а в ячейке С3 вычислим значение функции f(x n) для этого приближения.

3. Выберем команду:

Данные \ Работа с данными \ Анализ «что-если»\ Подбор параметра.

4. В окне «Подбор параметра»сделаем установки, как показано на рис.2.13 и нажмем кнопку ОК.

Рис.2.13. Решение нелинейного уравнения с помощью надстройки «Подбор параметра»

Если все было проделано правильно, то в ячейке В2 (рис.2.13) будет получено приближенное значение корня нашего уравнения.

Проделайте все эти операции ещё раз с другим значением начального приближения, например х 0 =4,5.

Контрольные вопросы

1. Какое уравнение называется нелинейным. Что является решением нелинейного уравнения.

2. Геометрическая интерпретация решения нелинейного уравнения.

3. Методы решения нелинейного уравнения (прямые и итерационные), в чем разница.

4. Два этапа численного решения нелинейного уравнения. Какие задачи ставятся на первом и втором этапах.

5. Первый этап решения нелинейного уравнения. Как выбирается нулевое приближение (нулевая итерация).

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

7. Геометрическая интерпретация численных методов решения нелинейного уравнения: половинного деления, Ньютона (касательных), хорд.

Глава 3.

Задание: дано нелинейного уравнения f(x) = 0 на заданном отрезке . Требуется средствами табличного процессора Excel найти корни данного уравнения методом касательных с использованием циклических ссылок.

x-x 3 +1=0 a=1 b=2

Решение:

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

Для включения режима циклических вычислений в Excel 2003 в меню Сервис/Параметры/вкладка Вычисления следует поставить флажок Итерации и флажок выбора вида ведения вычислений: автоматически. В MS Excel 2010 следует зайти в меню Файл/Параметры/Формулы и поставить флажок в поле "Включить итеративные вычисления" :

Найдем производную функции f(x)=x-x 3 +1

f’(x)=1-3x 2
В ячейку А3 введем значение а =1, ячейку В3 введем формулу расчета текущего значения х: =ЕСЛИ(B3=0;A3;B3-(B3-СТЕПЕНЬ(B3;3)+1)/(1-3*СТЕПЕНЬ(B3;2)))
В ячейку С3 введем формулу для контроля значения f(x): =B3-СТЕПЕНЬ(B3;3)+1.
Получим корень уравнения в ячейке В3 х=1,325.

Введем начальное приближение в ячейку А3 =2. Но для того чтобы вычисления были правильные, недостаточно изменить число в ячейке А3 и запустить процесс вычислений. Потому что в этом случае вычисления продолжаться с последнего вычисленного ранее значения. Это значение, в ячейке В3, необходимо обнулить, для этого можно заново записать туда формулу или просто выбрать ячейку с формулой и дважды щелкнуть мышью на ней. После этого поставить курсор на ячейку с формулой и нажать клавишу Enter для запуска процесса итерационных вычислений.

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

Пусть после взятия производной мы пришли к уравнению tg(x)=1/x . Проведем следующие преобразования:
tg(x)=1/x Ю x tg(x)=1 Ю x2 tg=1 Ю x2= 1 / tg(x) Ю x = ± .

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

В самом деле, мы прекрасно решаем квадратные и биквадратные уравнения, наипростейшие тригонометрические и степенные. Еще водятся "мастодонты", знающие о существовании формул Кардано для кубических уравнений. В общем же случае надежд на простое аналитическое решение нет. Более того, доказано, что даже алгебраическое уравнение выше четвертой степени неразрешимо в элементарных функциях. Поэтому решение уравнения проводят численно в два этапа (здесь разговор идет лишь о вещественных корнях уравнения). На первом этапе производится отделение корней - поиск интервалов, в которых содержится только по одному корню. Второй этап решения связан с уточнением корня в выбранном интервале (определением значения корня с заданной точностью).

1.1. Отделение корней

В общем случае отделение корней уравнения f(x)=0 базируется на известной теореме, утверждающей, что если непрерывная функция f(x) на концах отрезка имеет значения разных знаков, т.е. f(a)ґ f(b)Ј 0 , то в указан-ном промежутке содержится хотя бы один корень. Например, для уравнения f(x)= x 3 -6x+2=0 видим, что при x®Ґ f(x)>0 , при x®-Ґ f(x) , что уже свидетельствует о наличии хотя бы одного корня.

В общем случае выбирают некоторый диапазон, где могут обнаружиться корни, и осуществляют "прогулку" по этому диапазону с выбранным шагом h для обнаружения перемены знаков f(x) , т.е. f(x)ґ f(x+h) .

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

1.2. Уточнение корней методом половинного деления (дихотомии)

Самым простейшим из методов уточнения корней является метод половинного деления, или метод дихотомии, предназначенный для нахождения корней уравнений, представленных в виде f(x)=0 .

Пусть непрерывная функция f(x) на концах отрезка имеет значения разных знаков, т.е. f(a)ґ f(b) Ј 0 (), тогда на отрезке имеется хотя бы один корень.

Возьмем середину отрезка с=(a+b)/2 . Если f(a)ґ f(c) Ј 0 , то корень явно принадлежит отрезку от a до (a+b)/2 и в противном случае от (a+b)/2 до b .

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

Так как каждое очередное вычисление середины отрезка c и значения функции f(c) сужает интервал поиска вдвое, то при исходном отрезке и предельной погрешности e количество вычислений n определяется условием (b-a)/2 n e , или n~log 2 ((b-a)/e ) . Например, при исходном единичном интервале и точности порядка 6 знаков (e ~ 10 -6 ) после десятичной точки достаточно провести 20 вычислений (итераций) значений функции.

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

1.3. Уточнение корней методом хорд

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

Рис. 3. Метод хорд

Здесь вычисляются значения функции на концах отрезка, и строится "хорда", соединяющая точки (a,f(a)) и (b,f(b)) . Точка пересечения ее с осью абсцисс

принимается за очередное приближение к корню. Анализируя знак f(z) в сопоставлении со знаком f(x) на концах отрезка, сужаем интервал до [a,z ] или [z,b ] и продолжаем процесс построения хорд до тех пор, пока разница между очередными приближениями не окажется достаточно малой (в пределах допустимой погрешности) |Z n -Z n-1 |e .

Можно доказать, что истинная погрешность найденного приближения:

Где X * - корень уравнения, Z n и Z n+1 - очередные приближения, m и M - наименьшее и наибольшее значения f(x) на интервале [a,b ].

1.4. Уточнение корней методом касательных (Ньютона)

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

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

Пусть известно некоторое приближенное значение Z n корня X * . Применяя формулу Тейлора и ограничиваясь в ней двумя членами, имеем

откуда

.

Геометрически этот метод предлагает построить касательную к кривой y=f(x) в выбранной точке x=Z n , найти точку пересечения её с осью абсцисс и принять эту точку за очередное приближение к корню ().

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

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

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

.

Существуют и другие модификации метода Ньютона.

1.5. Уточнение корней методом простой итерации

Другим представителем итерационных методов является метод простой итерации .

Здесь уравнение f(x)=0 заменяется равносильным уравнением x=j (x) и строится последовательность значений