Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Информатика_1 / C / lecture4 / lecture4
.html<HTML
><HEAD
><TITLE
></TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.56"></HEAD
><BODY
CLASS="BOOK"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="BOOK"
><A
NAME="AEN1"
></A
><DIV
CLASS="TOC"
><DL>
<A HREF="#AEN2"> <H1>Лекция 4. Методы решения нелинейных уравнений. </H1></A>
<B >Table of Contents</B> <PRE>
<A HREF="#AEN154" > 1. Метод простых итераций. </A>
<A HREF="#AEN254" > 2. Метод Ньютона (касательных). </A>
<A HREF="#AEN354" > 3. Метод хорд.</A>
<A HREF="#AEN454" > 4. Метод деления отрезка пополам (бисекций). </A>
<A HREF="#AEN554" > 5. Задачи. </A> </PRE>
</DL
></DIV
><DIV
CLASS="LOT"
><DL
CLASS="LOT"
><DT
><B
>List of Figures</B
></DT
><DT
>1. <A
HREF="#AEN10"
>Геометрическая интерпретация метода простых итераций</A
></DT
><DT
>2. <A
HREF="#AEN16"
>Блок-схема для решения уравнения x-f(x)=0 методом простых итераций</A
></DT
><DT
>3. <A
HREF="#AEN24"
>Геометрическая интерпретация метода Ньютон для решения нелинейного уравнения F(x)=0</A
></DT
><DT
>4. <A
HREF="#AEN32"
>Блок- схема программы для решения нелинейного упавнения F(x)=0 методом Ньютона</A
></DT
><DT
>5. <A
HREF="#AEN42"
>Геометрическая интерпретация метода хорд для решения нелинейного уравнения F(x)=0</A
></DT
><DT
>6. <A
HREF="#AEN46"
>Блок-схема программы для решения нелинейного уравнения F(x)=0 методом хорд</A
></DT
><DT
>7. <A
HREF="#AEN54"
>Блок-схема программы для решения уравнения F(x)=0 методом бисекций</A
></DT
></DL
></DIV
><DIV
CLASS="CHAPTER"
>
<HR><B><A NAME="AEN2"> Лекция 4 </A>
</B>
<P> </P>
</DIV>
<PRE
CLASS="PROGRAMLISTING"
>В этой лекции рассматриваются методы решения нелинейных уравнений вида F(x)=0.
Приводятся блок-схемы и примеры программ.
Будут рассмотрены четыре метода - метод простых итераций,
метод касательных (называемый также методом Ньютона),
метод хорд и метод бисекций.
</PRE
><DIV CLASS="FORMALPARA" >
<HR><H2><A NAME="AEN154">
<P><B> Метод простых итераций. </B></P>
</A>
</H2>
</DIV>
<PRE
CLASS="PROGRAMLISTING"
>Метод простых итераций применяется для решения уравнений
частного вида, когда уравнение может быть записано в виде:
F(x) = x - f(x) =0.
На следующем рисунке приведена геометрическая интерпретация метода .
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN10"
></A
><P
><B
>Figure 1. Геометрическая интерпретация метода простых итераций
</B
></P
><P
><IMG
SRC="./iter.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>На рисунке показаны два графика для функций у=x и y=f(x). Точки
пересечения этих кривых определяют корни уравнения x - f(x) = 0.
Эти корни на рисунке обозначены r1 и r2. Для нахождения корня
методом простых итераций предлагается следующая процедура.
Выберем произвольную точку x0 на оси x. Проведем перпендикуляр
из точки x0 до пересечения с кривой y=f(x). В качестве первого приближения
к корню возьмем точку x1=y(x0). Из точки x1 проведем
перпендикуляр до пересечения с кривой y=f(x). В качестве второго
приближения к корню выберем точку x2=f(x1). Продолжая этот
процесс можно видеть , что каждое последующее приближение к
корню определяется через предыдущее по формуле
</PRE
><IMG
SRC="./formula_iter.jpg"><PRE
CLASS="PROGRAMLISTING"
>Справедливо следующее утверждение (без доказательства):
Если |df(x)/dx|<1 в точке пересечения графиков y=x и y=f(x), тогда
итерационный процесс (4.1) сходится к этой точке.
В нашем примере такой точкой является точка x=r1. Такие корни
называются притягивающими для метода простых итераций.
Корень r2 в нашем примере является отталкивающим и не может
быть найден методом простых итераций (4.1). Таким образом
очевидным недостатком метода простых
итераций является то , что не все корни уравнения x-f(x)=0 могут
быть с его помощью найдены.
Блок-схема алгоритма для решения уравнений методом простых
итераций :
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN16"
></A
><P
><B
>Figure 2. Блок-схема для решения уравнения x-f(x)=0 методом простых итераций
</B
></P
><P
><IMG
SRC="./Block-shem_it.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>Пример программы , реализующией приведенный выше алгоритм,
для решения уравнения x=ln(x)+2. Текст программы хранится в файле
<A HREF=l4_1.c> l4_1.c </A>
/* Включаем заголовки необходимых функций в программу */
#include <stdio.h>
#include<math.h>
#include<conio.h>
/* необходимо объявить заголовок функции , определяющей уравнение
x-f(x)=0 */
double f(double);
#define QUIT if( kbhit() ) if( getch()=='q' ) break
//Начало описания функции main
int main(void) {
double x,eps;
printf("input x,eps-->");
scanf("%le%le",&x,&eps);
while(fabs(x-f(x))>eps) { x=f(x); QUIT; }
printf("root=%e error=%e\n",x,x-f(x));
return 0;
}
// Описание функции f(x), которая в нашем случае должна возвращать
// значение ln(x)+2
// в библиотеке математических функций функция для вычисления
// натурального логарифма имеет имя log
double f(double x){
return log(x)+2;
}
Заметим , что в приведенной программе нам впервые потребовалось
описать кроме main еще одну функцию для вычисления f(x).
В начале программы дан загодовок этой функции -
double f(double); ,
а в конце программы приведено ее описание.
</PRE
><DIV
CLASS="FORMALPARA">
<HR><H2><A NAME="AEN254">
<P
><B
> Метод касательных (Ньтона) для решения нелинейных уравнений
. </B
>
</P
>
</A></H2>
</DIV
><PRE
CLASS="PROGRAMLISTING"
>В методе Ньютона решается уравнение F(x)=0. На следующем рисунке
показана геометрическая интерпретация метода Ньютона для решения
нелинейных уравнений.
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN24"
></A
><P
><B
>Figure 3. Геометрическая интерпретация метода Ньютон для решения нелинейного уравнения F(x)=0
</B
></P
><P
><IMG
SRC="./newton_geom.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>Алгоритм метода Ньютона для поиска корней уравнения F(x)=0 состоит
в следующем.
1. Выберем произвольную точку x0 на оси x и погрешность eps определения корня.
2. Проведем касательную к функции F(x) в точке (x0,F(x0)).
Определим точку , в которой касательная пересекает линию y=0.
Обозначим эту точку x1.
3. Вычислим значение функции F(x) в точке x1. Если |F(x1)|>eps
или |x0-x1|>eps тогда в качестве новой точки x0 выберем x1 (т.е. x0=x1)
и перейдем к пункту 2. Если |F(x1)|<eps и |x0-x1|<eps - считаем ,
что корень найден с требуемой погрешностью eps и выход из программы.
Уравнение касательной к функции F(x) в точке (x0,F(x0)) имеет вид:
</PRE
><IMG
SRC="./kasat.jpg"><PRE
CLASS="PROGRAMLISTING"
>Решая уравнение y(x1)=0 получим:
</PRE
><IMG
SRC="./newton_formula.jpg"><PRE
CLASS="PROGRAMLISTING"
>Блок схема программы для решения нелинейного уравнения методом Ньютона имеет вид:
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN32"
></A
><P
><B
>Figure 4. Блок- схема программы для решения нелинейного упавнения F(x)=0 методом Ньютона
</B
></P
><P
><IMG
SRC="./block_shema_newton.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>В этой блок-схеме через F1(x) обозначена функция вычисляющая производную от функции F(x).
Пример программы , соответствующий приведенной блок-схеме:
<A HREF=l4_2.c> (файл l4_2.c) </A>
//Пример программы для решения нелинейного уравнения
//F(x)=ln(x)+2-x=0
//методом Ньютона
#include <stdio.h>
#include<math.h>
#include<conio.h>
#include<stdlib.h>
// Заголовок функции для вычисления F(x)
double F(double);
// Заголовок функции для вычисления производной от функции F(x)
double F1(double);
#define QUIT if( kbhit() ) if( getch()=='q' ) exit(1)
int main(void) {
double x0,x1,eps;
printf("input x0,eps-->");
scanf("%le%le",&x0,&eps);
met1: x1=x0-F(x0)/F1(x0); QUIT;
if(fabs(F(x1))>eps||fabs(x0-x1)>eps){ x0=x1; goto met1;}
else printf("root=%e error=%e\n",x1,F(x1));
return 0;
}
//В заголовочном файле math.h функция для вычисления натурального
//логарифма
// имеет имя log
//Описание функции для вычисления F(x)
double F(double x){
return log(x)+2-x;
}
// Описание функции для вычисления производной от F(x)
double F1(double x) {
return 1.0/x-1;
}
В этой программе нам потребовалось кроме main ввести две новые
функции - для вычисления F(x) и ее производной. В начале программы
даны заголовки этих функций:
double F(double);
double F1(double);
из которых следует , что эти функции получают по одному
вещественному аргументу типа double и возвращают вещественные
значения тоже типа double.
В конце программы, после функции main, дано описание этих функций.
Кроме того в этой программе в макросе QUIT использована функция
exit вместо оператора break , использовавшегося нами ранее
для прерывания работы цикла. Дело в том , что в приведенном
примере нет циклов, а оператор break может использоваться только
в циклах. Поэтому вместо оператора break в макросе QUIT
использована функция exit - предназначенная для завершения
работы программы.
</PRE
><DIV
CLASS="FORMALPARA">
<HR><H2> <A NAME="AEN354">
<P
><B
> Метод хорд для решения нелинейных уравнений
. </B
>
</P>
</H2> </A>
</DIV
><PRE
CLASS="PROGRAMLISTING"
>Метод хорд применяют для решения нелинейных уравнений
F(x)=0 обычно в тех случаях , когда получить выражение для
производной dF(x)/dx либо трудно , либо оно имеет громоздкий вид. В
этом случае выражение для производной в формуле (4.3)
заменяют его разностным аналогом, после чего формула (4.3)
принимает вид:
</PRE
><IMG
SRC="./hord_formula.jpg"><PRE
CLASS="PROGRAMLISTING"
>Можно дать и геометрическую интерпретацию метода хорд.
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN42"
></A
><P
><B
>Figure 5. Геометрическая интерпретация метода хорд для решения нелинейного уравнения F(x)=0
</B
></P
><P
><IMG
SRC="./hord_geom.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>Для начала решения выбираются две произвольные точки на оси x.
На нашем рисунке это точки x0 и x1. Затем через две точки (x0,F(x0))
и (x1,F(x1)) проводистя хорда. Эта хорда пересекает линию y=0
в точке x2. Эта точка считается первым приближением к корню.
Далее , если |F(x2)|>eps или |(x0-x1)|>eps (eps - требуемая погрешность в
вычислении корня) , тогда точки x1 и x2 выбирают в качестве новых
стартовых точек , т.е. x0=x1, x1=x2 и вновь проводят хорду и т.д.
Критерием окончания итерационного прцесса считается достаточная
близость модуля значения функции |F(x2)| к нулю , а также достаточно
близкие значения двух поледовательных приближений к корню x0 и x1.
Чтобы найти в какой точке хорда , проведенная через точки (x0,F(x0))
и (x1,F(x1)) пересекает ось x-ов напишем уравнение этой хорды:
y(x)=F(x1) + (F(x1)-F(x0))*(x-x1)/(x1-x0).
Решая уравнение y(x2)=0, получаем формулу (4.4).
Блок-схема программы для решения уравнения F(x)=0 методом хорд
имеет следующий вид:
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN46"
></A
><P
><B
>Figure 6. Блок-схема программы для решения нелинейного уравнения F(x)=0 методом хорд
</B
></P
><P
><IMG
SRC="./block_shema_hord.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>И пример програмы, соответствующий приведенной блок-схеме:
<A HREF=l4_3.c> (пример содержится в файле l4_3.c) </A>
//Пример программы для решения нелинейного уравнения
//F(x)=ln(x)+2-x=0
//методом хорд
#include <stdio.h>
#include<math.h>
#include<conio.h>
#include<stdlib.h>
double F(double);
#define QUIT if( kbhit() ) if( getch()=='q' ) exit(1)
int main(void) {
double x0,x1,x2,eps;
printf("input x0,x1,eps-->");
scanf("%le%le%le",&x0,&x1,&eps);
met1: x2=x1-F(x1)*(x1-x0)/(F(x1)-F(x0));
x0=x1; x1=x2;
QUIT;
if(fabs(F(x2))>eps||fabs(x0-x1)>eps)goto met1;
else printf("root=%e error=%e\n",x1,F(x1));
return 0;
}
//В заголовочном файле math.h функция для вычисления натурального
//логарифма
// имеет имя log
double F(double x){
return log(x)+2-x;
}
</PRE
><DIV
CLASS="FORMALPARA">
<HR><H2> <A NAME="AEN454">
<P
><B
> Метод бисекций (или деления отрезка пополам)
. </B
>
</P>
</H2></A>
</DIV
><PRE
CLASS="PROGRAMLISTING"
>Метод бисекции для решения уравнения F(x)=0 можно начинать
если Вам известен такой отрезок [x0,x1] на границах которого
функция F(x) имеет разные знаки. Проверить , что функция имеет
разные знаки на концах отрезка [x0,x1] можно вычислив произведение
F(x0)*F(x1). Если у этого произведения отрицательный знак - значит
функция имеет разные знаки на концах отрезка. Разные знаки
функции на концах отрезка гарантируют, что внутри этого отрезка
имеется хотя-бы один корень. В этом случае применяется следующий
алгоритм поиска корня:
1. Находим середину отрезка x2=(x1+x0)/2.
2. Проверяем на какую половину отрезка попал корень.
Для этого проверяем знак произведения F(x0)*F(x2).
Если знак этого произведения меньше нуля - значит корень
попал на первую половину отрезка , т. е. на отрезок [x0,x2].
Тогда переносим точку x1 в x2.
Если знак произведения положителен - значит корень попал на вторую
половину отрезка т.е. на отрезок [x2,x1]. тогда переносим точку
x0 в x2.
Таким образом получаем новый отрезок [x0,x1], на котором
локализован корень и который в два раза меньше исходного.
3. Проверяем длину нового отрезка [x0,x1]. Если она меньше
требуемой точности определения корня - тогда окончание работы.
Если - же длина вновь полученного отрезка больше требуемой
точности определения корня, тогда переход на пункт 1.
В дальнейшем требуемую погрешность в определении корня
будем обозначать eps. Вот блок-схема программы для решения
уранения F(x)=0 методом бисекций:
</PRE
><DIV
CLASS="FIGURE"
><A
NAME="AEN54"
></A
><P
><B
>Figure 7. Блок-схема программы для решения уравнения F(x)=0 методом бисекций
</B
></P
><P
><IMG
SRC="./bissection_sheme.jpg"></P
></DIV
><PRE
CLASS="PROGRAMLISTING"
>И программа , написанная в соответствии с блок-схемой:
<A HREF=l4_4.c> (программа хранится в файле l4_4.c) </A>
//Пример программы для решения нелинейного уравнения F(x)=ln(x)+2-x=0
//методом бисекций
#include <stdio.h>
#include<math.h>
double F(double);
int main(void) {
double x0,x1,x2,eps;
printf("input eps-->");
scanf("%le",&eps);
met1: printf("input x0,x1-->");
scanf("%le%le",&x0,&x1);
if(F(x0)*F(x1)>0)goto met1;
met2: x2=(x1+x0)/2;
if(F(x0)*F(x2)<0)x1=x2; else x0=x2;
if(fabs(x0-x1)>eps)goto met2;
else printf("root=%e error=%e\n",(x1+x0)/2,F((x1+x0)/2));
return 0;
}
//В заголовочном файле math.h функция для вычисления натурального логарифма
// имеет имя log
double F(double x){
return log(x)+2-x;
}
</PRE
><DIV
CLASS="FORMALPARA"
><P
><B
> Задачи к лекции
. </B
>
</P
></DIV
><PRE
CLASS="PROGRAMLISTING">
<HR><A NAME="AEN554">
Задача 1. Переписать прграмму l4_1.c, используя вместо оператора
while оператор if.
Задача 2. Переписать программу l4_2.c используя вместо оператора
if оператор цикла while.
Задача 3. Переписать программу l4_3.c используя вместо оператора
if оператор цикла do.
Задача 4. Имеется уравнение
F(x)=ln(x)+a-x=0
Написать программу для вывода на экран таблицы корней этого
уравнения для а=2, 2.2,2.4,2.6,...3.6. Корни должны искаться методом
бисекций. В программе должен использоватся оператор switch.
</PRE>
</A>
</DIV>
<PRE>
<A HREF="../lecture3/lecture3.html" >previous</A> <A HREF="../lecture5/lecture5.html" >next</A> <A HREF="../index.html">home</A>
</PRE>
</BODY
></HTML
>
Соседние файлы в папке lecture4