Если функция f(x) непрерывна на отрезке [a,b] и принимает на его концах значения разных знаков, то на этом отрезке существует по крайне мере корень уравнения (2).
В качестве примера обратимся к уравнению (1), которое предварительно перепишем в виде
f(x)=x-cos(x)=0.
Функция f(x=x-cos(x) непрерывна на отрезке [0,1], а ее значения на концах отрезка имеют разные знаки:
f(0)=-1 <0, f(1)=1-cos(1) >0.
Отсюда сразу следует существование на отрезке [0,1] по крайней мере одного корня уравнения (1). Ранее к этому выводу пришли с помощью наглядных, но математически нестрогих геометрических соображений. Теперь этот вывод – прямое следствие сформулированной теоремы. Она не позволяет определить общего числа коней. Однако в данном случае это легко сделать с помощью дополнительных исследований.
Вычислим производную функцию f(x):
f(x)’=1+sin(x).
В интересующей нас области измерения переменной x: xÎ[0,1] она положительна. Следовательно, функция f(x) на отрезке [0,1] монотонно возрастает и может иметь только один корень.
Метод вилки
В основе метода лежит одно из самых простых и эффективных алгоритмов решения уравнения. Его основу составляет процесс построения по методу «артиллерийской вилки» последовательности вложенных друг в друга отрезков [an, bn]. Их концы образуют две монотонные последовательности, одна из которых { an, } («недолеты») сходятся к некоторой точке x =cснизу (an<с), вторая { bn, }(«перелеты») – сверху (bn>с).При выполнении условий теоремы, сформулированной выше, доказывается, что предельная точка x=c является корнем уравнения. Тем самым оказывается установленным факт существования решения этого уравнения на отрезке [a, b]. Сам процесс построения последовательности вложенных отрезков [an, bn], содержащих искомый корень x=c, позволяет найти его приближенное значение с любой точностью ε.
Описание метода
Предположим для определенности, что функция f(x) принимает на левом конце отрезка [a, b]отрицательное значение, на правом – положительное:
f(a)<0, f(b)>0.
Возьмем среднюю точку отрезка [a, b] ξ= (a+b)/2 и вычислим в ней значение функции f(x). Если f(x)=0, то утверждение теоремы доказано: мы нашли на отрезке [a, b] точку с= ξ, в которой наша функция обращается в нуль. В противном случае, когда f(x)≠0, поступим следующим образом: рассмотрим два отрезка [a, ξ] и [b, ξ] и выберем один из них, исходя из условия, чтобы функция f(x) принимала на его концах значения разных знаков. Выбранный отрезок обозначим [a1, b1]. По построению
f(a1) < 0, f(b1) >0.
Возьмем среднюю точку отрезка [a1, b1] ξ1= (a1+b1)/2 и опять вычислим в ней значение функции f( ξ1 ). Если f( ξ1)=0, то доказательство теоремы закончено. В противном случае f(x)≠0, снова рассмотрим два отрезка [a1, ξ], [b1, ξ] и выберем тот из них, на концах которого функция f(x) принимает значение разных знаков. Выбранный отрезок обозначим [a2, b2].По построению
f(a2) < 0, f(b2) >0.
Будем продолжать этот процесс. В результате либо он оборвется на некотором шаге n благодаря тому, что f( ξn)=0,либо будет продолжатьсянеограниченно. В первом случае вопрос о существовании корня уравнения решен. Рассмотрим второй случай.
Неограниченное продолжение процесса дает последовательность отрезков [a, b], [a1, b1], [a2, b2],...Эти отрезки вложены друг в друга: каждый последующий отрезок принадлежит всем предыдущим:
an ≤ an+1 <bn+1 ≤bn (3)
причем
f(an) < 0, f(bn) >0.
Длины отрезков с возрастанием номера n стремятся к нулю:
lim(bn-an)= lim(b-a)/2n =0
Рассмотрим левые концы отрезков {an}. Они образуют монотонную неубывающую ограниченную последовательность. Такая последовательность имеет предел, который мы обозначим через с1:
lim an = c1
Согласно лемме о переходе к пределу в неравенствах имеем
C1 ≤ bn (4)
Теперь рассмотрим правые концы отрезков {bn}. Они образуют монотонную не возрастающую ограниченную последовательность, которая тоже имеет предел. Обозначим этот предел через с2:
lim bn =c2
Согласно неравенству (4) и лемме эти пределы удовлетворяют неравенству c1 ≤ c2.
Итак, an ≤ c1 ≤ c2 ≤ bn
и, следовательно, c2 –c1 ≤ bn – an =(b-a)/2n
Таким образом, разность с2 – с1 меньше любого наперед заданного положительного числа. Это означает, что с2 – с1=0, т.е. с2 = с1=с
Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности. Используя непрерывность функции f(x), докажем, что она является корнем уравнения.
Мы знаем, что f(an) ≤ 0. Согласно определению непрерывности и возможности предельного перехода в неравенствах имеем
f(c)= lim f(an) ≤ 0 (5)
Аналогично, учитывая, что f(bn) ≥ 0.,получаем
f(c)= lim f(bn) ≥ 0.,. (6)
Из (5) и (6) следует, что
f(c)= 0,
т.е. с – корень уравнения. Теорема доказана.
Процесс построения последовательности вложенных стягивающих отрезков методом вилки является эффективным вычислительным алгоритмом решения уравнения. На n -м шаге процесса получаем
an ≤ c.
Это двойное неравенство показывает, что число an определяет искомый корень с с недостатком, а число bn – с избытком, с ошибкой, не превышающей длину отрезка ∆n = bn – an = (b-a)/2n.При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=1/2. Если задана необходимая точность ε (ε>0), то чтобы ее достигнуть, достаточно сделать число шагов N, удовлетворяющее условию:
N>log2 ((b-a)/ ε).
Пример. Рассмотрим отапливаемое помещение, которое имеет наружные ограждения площадью F = 50 м2, сопротивление теплопередачи составляет R=2,5 м2 оС/Вт. В помещении установлен отопительный прибор, поверхность которого составляет А=1,5 м2, температура подающей воды tг =95 оС, а обратной tоб =70 оС.
Требуется определить температуру внутреннего воздуха tв, при температуре наружного воздуха tн = –20 оС?
Для решения поставленной задачи составим уравнение характеризующее баланс тепловой энергии в помещении.
Потери теплоты через ограждающие конструкции могут быть определены по следующей формуле:
qт.п. =(tв – tн)F/R (п1)
Поступление теплоты от нагревательных приборов может быть определено по следующей формуле:
qпр = А qном (Δtср. /70)1+n (п2)
где qном – номинальный тепловой поток от отопительного прибора, Вт/м2 (qном=600 Вт/м2);
Δtср.= 0,5(tг + tоб) –tв;
n – коэффициент характеризующий теплоотдачу отопительного прибора (n=0,4).
Приравниваем формулу п1 и п2
(tв – tн)F/R= А qном (Δtср. /70)1+n. (п3)
После подстановки известных величин формула приобретет вид
(tв +20)50/2,5 =1,5*600*((82,5- tв)/70)1,4 (п4)
Решение данного уравнения для определения температуры внутреннего воздуха (tв) в общим виде представляет определенные затруднения, поэтому воспользуемся методом «вилки». Для этого выполним преобразования. Перенесем все члены уравнения в левую часть
(tв +20)50/2,5 – 1,5.600((82,5- tв)/70)1,4 =0.
Предварительный анализ свидетельствует, что данная функция неразрывна и может приобретать положительные и отрицательные значения.
Определим диапазон, на котором будем искать значение корня. При значении tв =10 oC, значение функции f(10)=-345,3191649. При значении tв =25 oC, значение функции f(25)=216,6546618. Можно утверждать, что на концах отрезка [10, 25] функция будет приобретать противоположные знаки, т.е. корень уравнения будет находиться на данном отрезке. Вычисление выполним в табличной форме.
Таблица 1
| N | an | bn | ξ= (a+b)/2 | f( ξn) |
| 17,5 | -61,30462678 | |||
| 17,5 | 21,25 | 78,45879455 | ||
| 17,5 | 21,5 | 19,5 | 13,42747243 | |
| 17,5 | 19,5 | 18,5 | -23,88430668 | |
| 18,5 | 19,5 | -5,214785699 | ||
| 19,5 | 19,25 | 4,109759286 | ||
| 19,25 | 19,125 | -0,551660239 | ||
| 19,125 | 19,25 | 19,1875 | 1,779262892 | |
| 19,125 | 19,1875 | 19,15625 | 0,613854653 | |
| 19,125 | 19,15625 | 19,140625 | 0,031110536 |
Результаты расчетов, связанных с девяти кратным делением исходного отрезка [10, 25] пополам даны в табл.1. Они определяют корень с с точностью ε < (25-10)/29 < 0,029297.
Мы можем утверждать, что искомый корень уравнения принадлежит отрезку [19,125, 19,15625].
Метод итераций
(метод последовательных приближений)
Предположим, что уравнение можно записать в виде
x=φ(x).
Возьмем произвольное значение xo из области определения функции φ(x) и будем строить последовательность чисел {xn}, определенных с помощью рекуррентной формулы:
xn+1 = φ(xn), n= 0, 1, 2, 3,...
Последовательность {xn} называется итерационной последо-вательностью. При ее изучении встают два вопроса:
1. Можно ли процесс вычисления чисел xn продолжать неограниченно, т.е. будут ли числа xn принадлежать области определения функции φ(x)?
2. Если итерационный процесс бесконечен, то как ведут себя числа xn при n→ ∞?
При определенных ограничениях на функцию φ(x ) итерационная последовательность является бесконечной и сходится к корню уравнения:
xn =c, c= φ(c).
Функция φ(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная α, что для любых x1 и x2, принадлежащих отрезку [a, b], имеет место неравенство
| φ(x1)- φ(x2)| ≤ α | x1 – x1 |.
Величину α в этом случае называют постоянной Липшица.
Если функция φ(x) удовлетворяет на отрезке [a, b]условию Липшица, то она непрерывна на этом отрезке.
Пусть xo - произвольная точка отрезка. Рассмотрим приращение функции φ(x) в этой точке
Δf =f(xo+ Δx) – f(xo).
Оценим его с помощью неравенства
| Δf| | ≤ α |Δ x|.
Таким образом, lim Δf =0, что означает непрерывность функции.
Условие Липшица имеет простой геометрический смысл. Возьмем на графике функции y= f(x) две произвольные точки: М1 с координатами (x1, f(x1)) и М2 с координатами (x2, f(x2)) (рис.3). Напишем уравнение прямой линии, проходящей через эти точки. Оно имеет вид
y=f(x1)+k(x-x1),
где k – тангенс угла наклона прямой к оси x –определяется по формуле
k = (f(x1)- f(x2))/(x1 –x2).
Если функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек М1 и М2 будем иметь: |k|≤α. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведенных через всевозможные пары точек графика функции y= f(x).
Рис.3. Геометрическая иллюстрация условий Липшица
Сделаем следующий шаг – предположим, что функция f(x) имеет на отрезке [a, b] ограниченную производную: |f’(x)|≤m при xÎ[a, b]. Можно доказать, что в этом случае она удовлетворяет условию Липшица с постоянной α=m. Данное уравнение также имеет простой геометрический смысл- каждой секущей графика функции y= f(x) можно сопоставить параллельную ей касательную (рис.4). Поэтому наибольший тангенс угла наклона секущих не превосходит наибольшего тангенса угла наклона касательных, и его можно оценить той же константой m: |k|≤m. Таким образом, любая функция f(x) с ограниченной производной обязательно удовлетворяет условию Липшица.
Рис. 4. Геометрическая иллюстрация связи условия Липшица с предположением о дифференцируемости функции f(x)
Сходимость итерационной последовательности к корню уравнения может быть использована для приближенного определения этого корня с любой степенью точности. Для этого нужно только провести достаточное число итераций.
Рассмотрим в качестве примера, иллюстрирующего данный метод, уравнение, представленное в примере предыдущего раздела (п4).
(tв +20)50/2,5 =1,5.600.((82,5- tв)/70)1,4
Данное уравнение можно представить в следующем виде
tв =45.((82,5- tв)/70)1,4 -20
Роль функции φ(x) в нем играет 45.((82,5- tв)/70)1,4 -20. Это – дифференцируемая функция, которая имеет производную на отрезке [10, 25]. / φ’(x) / =0,9((82,5-tв)/70)0,4 ≤ 0,9((82,5-10)/70)0,4
Таким образом, функция удовлетворяет на отрезке [10, 25] условию Липшица с постоянной α=0,9((82,5-10)/70)0,4 <0,912722.
Результаты вычислений по рекуррентной формуле, которая в нашем случае принимает вид xn+1 =45.((82,5-xn)/70)1,4 -20, даны в табл.2. За нулевое приближение была выбрана средняя точка отрезка xo =17,5.
Для удобства анализа итерационной последовательности ее члены расположены по два в строке. В результате образовались столбцы членов с четными и нечетными номерами. Сравнивая их между собой, видим, что четные члены меньше нечетных: итерационная последовательность скачет то вверх, то вниз. С возрастанием номера четные члены возрастают, а нечетные – убывают, приближаясь друг к другу. Такое поведение последовательности означает, что корень уравнения лежит между четными и нечетными итерациями, первые дают его значение с недостатком, вторые - с избытком. Это позволяет легко контролировать точность, достигнутую после любого числа итераций: погрешность не превышает разности между последними вычислениями нечетным и четным членами.
Таблица 2
| n | X2n | X2n+1 |
| 17,5 | 20,56523134 | |
| 17,91260145 | 20,20519447 | |
| 18,22150871 | 19,93624264 | |
| 18,45273279 | 19,73526403 | |
| 18,62577857 | 19,58504337 | |
| 18,75526581 | 19,47274218 | |
| 18,85214805 | 19,38877819 | |
| 18,92462892 | 19,3259953 | |
| 18,97885068 | 19,27904717 | |
| 19,01941101 | 19,24393831 | |
| 19,04975081 | 19,21768218 | |
| 19,0724448 | 19,19804602 | |
| 19,08941941 | 19,18336044 | |
| 19,10211583 | 19,17237717 | |
| 19,11161219 | 19,16416274 |
Мы остановили процесс вычисления на 29-й итерации и можем написать для корня с двойное неравенство:
x28 =19,11161219<c< x29 =19,16416274,
т.е. члены итерационной последовательности x28 и x29 определяют с с недостатком и избытком с погрешностью которая не превышает разность x28 - x29:
ε<Δ29 = x28 - x29 <0,05.
Точность, которой мы достигли после 29 итераций оказалась несколько ниже, чем после 9 шагов в методе вилки. Причина такого различия ясна. В обоих методах погрешность убывает по закону геометрической прогрессии. Для метода вилки знаменатель прогрессии равен ½, он не зависит от вида функции f(x). Для метода итераций знаменатель равен α – постоянная Липшица функции φ(x). В рассматриваемом примере α>1/2, поэтому сходимость итераций медленнее сходимости метода вилки. Это означает, что метод итераций имеет преимущество перед методом вилки с точке зрения скорости сходимости только в том случае, когда α<1/2.
Метод касательных
(метод Ньютона)
Метод касательных связанный с именем Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Предположим, что функция f(x), имеющая корень с на отрезке [a, b], дифференцируема на этом отрезке и ее производная f`(x) не обращается на нем в нуль. Возьмем произвольную точку xo и напишем в ней уравнение касательной к графику функции f(x):
y = f(xo)+f`(xo)(x-xo).
График функции f(x) и ее касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью x будет расположена недалеко от корня с (рис. 5).
Рис. 5. Построение последовательности по методу касательных
Для определения точки x1 имеем уравнение
f(x o ) + f `(x o )(x 1 -x o )=0
Таким образом,
x 1 = x o - f(x o )/f `(x o )
Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x = x 1 и найдем для нее точку пересечения x2 с осью x (рис. 5):
x 2 = x 1 - f( x1 )/f `(x 1 ).
Продолжая этот процесс, получим последовательность {xn}, определенную с помощью рекуррентной формулы:
xn+ 1 =xn - f(xn)/f `(xn), n= 0, 1, 2 ,...
При исследовании этой последовательности, как и последовательности метода итераций, встают два вопроса:
1. Можно ли процесс вычисления чисел xn продолжать неограниченно, т.е. будут ли числа xn принадлежать отрезку [a, b]?
2. Если итерационный процесс бесконечен, то как ведет себя последовательность {xn} при n→ ∞?