Файл: Ташкенский университет информационных технологий имени мухаммада алхорезми нурафшанский филиал.pptx

ТАШКЕНСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛ-ХОРЕЗМИ НУРАФШАНСКИЙ ФИЛИАЛ

Кафедра. К.И.Ф

Тема:Алгоритмы ветвления. Методы приближенного решения алгебраических и трансцендентных уравнений. Оценка эффективности. Итерационные циклы

Названия группы: 620-21 Ф.И студента:Илесов Рафик

Ташкент 2023

План:

1. Алгоритмы ветвления

2. Приближенные решения алгебраических и трансцендентных уравнений

3. Итерационные циклы

4. Литература

Начало

Ввод/вывод данных

Условие

Команда (действие)

Счетчик цикла

Конец

Начало алгоритма, вход в программу

Конец алгоритма, выход из программы

Ввод исходных данных или вывод результата

Выполнение действий

Проверка логического условия

Количество повторов цикла

Общий вид блок-схем алгоритмической структуры “ветвление”

Действие 1

Условие

Действие 2

Условие

• Разветвляющимся называется алгоритм в котором порядок выполнения действий зависит от некоторого условия.

В Паскале ветвление организуется с помощью двух операторов: IF и CASE.

условие

действие1

действие2

условие

действие1

Оператор IF

Составить алгоритм планирования выходного дня студентом: если будет хорошая погода, он пойдет гулять, а если плохая − будет писать реферат.

Входные данные: x (информация о погоде);

Выходные данные: y (результат прошедшего выходного дня).

program Student;

var x, y;

begin

writeln(‘Хорошая погода?');

read ({Да});

if Y:={Да} then Y:={Студент идет гулять}

else Y:={Студент пишет реферат};

writeln (‘Как студент провел свой выходной?’, Y);

---

end.

Постановка задачи

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

f(x)=0 (1)

Опр.1 Число t называется корнем уравнения (1) или нулем функции f, если при подстановке его вместо х уравнение превращается в верное равенство

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

• Установить, имеет ли оно действительные корни и их количество;

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

Опр.2. Поиск приближенного значения корня с точностью до заданного достаточно малого числа ε>0 называется уточнением корня. Задача уточнения будет решена, если найдется число х* такое, что

׀ t-x*׀ ≤ε. Тогда t≈ х* с точностью до ε

Геометрическая интерпретация

Пусть дано уравнение y=f(x). Построим график функции y=f(x)

x

y

t1

t2

t3

y = f(x)

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

Найдем корни уравнения sin4x – lnx = 0 Преобразуем его к виду sin4x = lnx

• Графики функций у=sin4x и у = lnx

x

y

t1

t2

t3

y = sin 4x

y = ln x

t1≈0,8 t2≈1,7 t3≈2,1

• Отделение корней
• Уточнение корней до заданной степени точности

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

Опр.3 Отделение корней- это определение их наличия, количества и нахождение для каждого из них достаточно малого отрезка [a,b], которому он принадлежит

Теорема (о единственности корня). Если функция f(x) определена, непрерывна, монотонна на отрезке [a,b] и принимает на концах отрезка значения разных знаков, т.е f(a)f(b)<0, то существует единственная точка t(a,b), в которой значение функции равно нулю

Графически корни можно отделить 2-мя способами

• 1 способ Отделение корней на графике f(x) Построить график функции y=f(x) и определить координаты пересечений с осью Ох – это приближенные значения корней уравнения

---

y=f(x)

x

y

x1*

a

b x2* x3*

На графике 3 корня.

Первый корень

x*  [a,b]

2 способ Отделение корней по графикам функций (x) и (x).

Преобразовать f(x)=0 к виду (x) = (x), где (x) и (x) – элементарные функции, и определить абсциссу пересечений графиков этих функций.

На графике 2 корня.

Первый корень

x1*  [a,b]

y

x

y=(x)

y= (x)

x1*

a

b x2*

Уравнение имеет два корня: t1[0,5; 1], t2[2,5; 3].

t1 1

2

t2

3

1

-1

-2

g(x)= -x2+3x-2

φ(x)=2cos(x+π/3)

Блок-схема алгоритма отделения корней уравнения f(x)=0

Метод половинного деления

Пусть дано уравнение f(x)=0.

Будем считать, что отделение корней произведено и на отрезке [a; b] расположен один корень t. Требуется найти приближенное значение корня с точностью до , где  – достаточно малое положительное число.

Разделим [a; b] пополам точкой с и вычислим f(c). Проверим следующие условия:

• Если f(c)=0, то c – корень. t=c.
• Если f(a) f(c)<0, то корень лежит в интервале [a; c].
• Если f(c) f(b)<0, то корень лежит в интервале [b; c].
Выберем ту половину отрезка, на концах которой функция принимает значения разных знаков, и обозначим ее [a1; b1]. Затем отрезок [a1; b1] делим пополам точкой и проводим аналогичные рассуждения. Получится либо точный корень t=c1, либо отрезок [a2; b2] со свойством f(a2) f(b2)<0. И так далее.

Геометрическая интерпретация метода половинного деления

x

y

y=f(x)

a

b

c1

b1

a1

c

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

• Для того, чтобы найти приближенное значение корня с точностью до >0, необходимо остановить итерационный процесс половинного деления на таком шаге n, где bn– an 2. Тогда за приближенное значение корня можно взять величину

с точностью , так как

x

an

bn

x*

t





2

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

---

или

Блок-схема алгоритма уточнения корня уравнения f(x)=0 на отрезке [a;b] с точностью  методом половинного деления

СХОДИМОСТЬ АЛГОРИТМА [convergence of algorithm] — способность алгоритма приводить к результату за конечное число шагов.

Скорость сходимость алгоритма  один из важных показателей качества экономико - математических моделей, предназначенных для решения задач  на ЭВМ.

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

Итерационные циклы

Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно.

Для его организации используется цикл типа  «пока».

Выход из итерационного цикла осуществляется в случае выполнения заданного условия.

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

В противном случае произойдет "зацикливание" алгоритма, т.е. не будет выполняться основное свойство алгоритма — «результативность».

Вычисление сумм — типичная циклическая задача. 

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

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

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

Литература:

• https://ppt-online.org/101875

2. http://www.myshared.ru/slide/1407140/

Спасибо за внимание!

---