- •Задачи учебной дисциплины
- •Основные понятия
- •Системы счисления
- •Двоичная, десятичная и шестнадцатеричная системы
- •Перевод целых чисел
- •Перевод дробных чисел
- •Логические основы эвм
- •Логические операции
- •Логические функции
- •Классификация эвм
- •По принципу действия
- •По назначению
- •По этапам создания
- •Лекция 2
- •Структурная схема эвм.
- •Микропроцессор
- •Системная шина
- •Постоянное и оперативное зу
- •Внешние зу
- •Магнитные носители
- •Оптические носители
- •Флэш-память
- •Видеоподсистема эвм
- •Видеокарта
- •Монитор
- •Контроллеры портов ввода-вывода
- •Периферийные устройства
- •Клавиатура
- •Манипулятор типа «мышь»
- •Принтеры
- •Сканеры
- •Сетевой адаптер
- •Лекция 3
- •Программное обеспечение эвм
- •Классификация программного обеспечения
- •Операционные системы
- •Распределение ресурсов эвм между процессами
- •Поддержание файловой системы
- •Обеспечение интерфейса пользователя
- •Драйверы устройств
- •Лекция 4
- •Понятие алгоритма
- •Алгоритмизация
- •Словесная запись алгоритмов
- •Схемы алгоритмов
- •Технология разработки алгоритмов
- •Разработка программы
- •Отладка и тестирование программы
- •Причины и типы ошибок
- •Способы и средства отладки
- •Отладка программ в среде Delphi
- •Точки контрольного останова
- •Окно наблюдения
- •Принудительное прерывание работы программы
- •Трассировка программы
- •Действия в точках прерывания
- •Группировка точек прерывания
- •Вычисление выражений и изменение значений
- •Ведение протокола работы программы
- •Лекция 5
- •Алгоритмы вычисления определенных интегралов.
- •Метод прямоугольников.
- •Формулы Ньютона-Котеса
- •Формула трапеций.
- •Формула парабол (Симпсона)
- •Формула Ньютона (правило трех восьмых)
- •Алгоритм вычисления суммы бесконечного ряда
- •Алгоритмы нахождения корней уравнений.
- •Метод итераций
- •Метод половинного деления
- •Метод касательных
- •Метод хорд
- •Алгоритмы обработки массивов
- •Алгоритм обработка записей
- •Лекция 6
- •Вычислительные сети
- •Модель взаимодействия открытых систем
- •Сетевые протоколы
- •Топологии вычислительных сетей
- •Виды коммутации
- •Способы адресации эвм в сети
- •Маршрутизация
- •Лекция 7
- •Глобальная сеть
- •Протоколы сети Интернет
- •Система адресации в Интернет
- •Службы сети Интернет
- •Электронная почта
- •Служба www
- •Служба передачи файлов
- •Лекция 8
- •Базы данных и субд
- •Свойства базы данных
- •Реляционная модель данных
- •Нормализация отношений
- •Типы связей
- •Операции над отношениями
- •Список дополнительной литературы
Алгоритмы нахождения корней уравнений.
Решение алгебраических уравнений численными методами состоит из двух этапов:
– отделение корней, т. е. отыскание достаточно малых интервалов (a, b), в каждом из которых заключен один и только один корень;
– вычисление (уточнение) корня с заданной погрешностью.
Для отделения корней можно использовать алгоритм, схема которого приведена на рис. 5.9. На втором этапе используется один из известных алгоритмов уточнения значения корня. При этом любой из известных алгоритмов реализует вычисления в соответствии с итерационным циклом. Рассмотрим более подробно эти алгоритмы.
Метод итераций
Пусть задано уравнение f(x) = 0, имеющее один-единственный корень х на интервал (a, b), т. е. a ≤ x ≤ b.
Уравнение f(x) = 0 представим в виде, необходимом для реализации метода итерации x = φ(x).
Если в интервале (a, b) выполняется неравенство |φ'(x)| ≤ q < 1, то метод итерации применим к исходному уравнению, и приведет к уточнению корня с заданной точностью (процесс итерации сходится).
Приведение исходного уравнения f(x) = 0 к форме x = φ(x).может быть выполнено разными способами. Один из них сводится к следующему. Предположим, что 0 ≤ m ≤ f(x) ≤ M при a ≤ x ≤ b (если f(x) < 0, то достаточно уравнение f(x) = 0 умножить почленно на -1), тогда уравнение
равносильно исходному уравнению f(x) = 0, имеет требуемую каноническую форму и
На рис. 5.11,а показан геометрический смысл первоначального уравнения f(x)=0. На этом рисунке точка х* является искомой. В результате тождественных преобразований исходного уравнения f(x)=0 к требуемому виду получаем геометрический смысл итерационного метода. На рис. 5.11,б искомый корень х* определяет точку пересечения двух функций: у = х и у =φ(х).
Метод итерации состоит из последовательности следующих шагов: выбираем любое значение х = х0 из интервала (a, b), вычисляем φ(х0) и приравниваем его к новому значению корня x1:
Далее этот процесс повторяется так, что k-я итерация состоит в вычислении
Погрешность εk на k-й итерации удовлетворяет неравенству
Процесс итерации проводим до тех пор, пока погрешность εk будет больше заданной погрешности ε. На рис. 5.11,б прямые со стрелками показывают итерационное движение вычислительного процесса к искомому значению х*.
В алгоритме метода итераций вычисляется последовательность значений
х0, х1, х2, …, хn, …
по формуле xn = φ(xn-1). Данная последовательность сходится к величине х*. Условие продолжения цикла
|xn – xn-1| > ε,
т.е. вспомогательная последовательность для контроля погрешности:
|x1 – x0|, |x2 – x1|, …, |xn – xn-1|, … .
Заметим, что в качестве вспомогательной можно использовать последовательность
|f(x0)|, |f(x1)|, |f(x2)|, …, |f(xn)| … ,
которая сходится к нулевому значению.
Рис. 5.19. Алгоритм вычисления определенного
интеграла по формуле Ньютона
Рис. 5.19. Алгоритм вычисления определенного
интеграла по формуле Ньютона
Рис. 5.11. Геометрическая иллюстрация
метода итераций
Рис.
5.19. Алгоритм вычисления определенного
интеграла
по формуле Ньютона
0
a
x* b x
φ(x2)
φ(x1)
φ(x0)
Поэтому условием продолжения цикла с предусловием может быть неравенство
Пусть, например, необходимо найти с погрешностью ε = 10-4 корень уравнения
Приведем исходное уравнение к виду
Для определения x0 применим графический метод отделения корней, а именно построим график функций
Нетрудно убедиться, что корень (точка пересечения этих графиков) принадлежит к отрезку [0, 1]. Поэтому
для всех метод итераций применим.