- •1.Предмет и задачи информатики
- •1) Теоретическая информатика:
- •2) Средства информатизации:
- •3) Информационные технологии
- •4) Социальная информатика:
- •2. Истоки и предпосылки информатики.
- •3. Структура современной информатики
- •4. Понятие информации. Носители информации. Сигналы
- •5. Количество информации. Измерение информации. Единицы измерения
- •6. Кодирование информации различных видов
- •7. Свойства информации
- •8. Устройство персонального компьютера
- •9. Основные принципы построения и работы компьютера
- •10. Понятие файла и файловой системы
- •11. Понятие информационной технологии
- •13. Основы интернета. Основные протоколы
- •14. Службы Интернета
- •15. Этапы решения задачи на эвм
- •16. Алгоритм. Свойства алгоритма
- •17. Методы проектирования алгоритмов
- •18. Способы описания алгоритмов. Основы графического способа.
- •19. Структуры алгоритмов. Основные виды вычислительных процессов. Примеры.
- •20. Алгоритмы вычисления суммы функционального ряда. Использование рекуррентных формул. Пример
- •Примеры
- •21. Поиск минимального и максимального элементов массива.
- •22. Сортировка одномерных массивов
- •23. Системы программирования и их состав.
- •24. Понятие о программировании
- •25. Понятие программного обеспечения. Классификация программного обеспечения.
- •26. Назначение операционной системы
- •27. Основные функции операционных систем
- •28. Прикладное по
- •29. Язык программирования Паскаль. Общая характеристика. Основные правила записи программ на языке Паскаль. Структура программы. Пример программы
- •6.Понятие типа данных в Турбо Паскаль
- •Простые типы данных
- •Численные (арифметические) выражения
- •Логические выражения
- •Символьные выражения
- •Составной оператор
- •30. Основные элементы языка Pascal
- •31. Понятие типа данных в Турбо Паскаль
- •Простые типы данных
- •Численные (арифметические) выражения
- •Логические выражения
- •Составной оператор
- •34. Ввод и вывод данных в Паскале.
- •Рассмотрим, для начала, Вывод данных в Паскале.
- •Рассмотрим, теперь, Ввод данных в Паскале.
- •35. Условные операторы Pascal-Паскаль
- •36. Оператор выбора Паскаля
- •37. Оператор безусловного перехода
- •38. Счетный оператор цикла или оператор цикла с параметром
- •39. Цикл с предпроверкой условия
- •40. Цикл с постпроверкой условия
- •42. Процедуры и функции
- •Описание и вызов процедур и функций
- •43. Процедуры.
- •44. Численное решение систем нелинейных уравнений
- •Методы численного решения уравнений и систем нелинейных уравнений
- •3.1. Решение нелинейных уравнений
- •3.1.2. Методы уточнения корней нелинейных уравнений
- •Тогда .
- •С погрешностью
- •Откуда при
- •Пусть тогда и
- •45. Метод половинного деления.
- •Тогда .
- •С погрешностью
- •46. Метод хорд
- •47. 52. Метод Ньютона (метод касательных)
- •48. Комбинированный метод хорд и касательных для уточнения корней нелинейных уравнений
- •49. 51. Метод простых итераций
- •50. Решение систем линейных алгебраических уравнений методом Гаусса
- •53. Метод прямоугольников
- •Составные квадратурные формулы
- •Составные формулы для равномерных сеток
- •Погрешность метода
- •Пример реализации
- •54. Метод трапеций
- •Составная формула
- •59. Интерполяцио́нный многочле́н Лагра́нжа
- •Определение
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •60. Разделё́нная ра́зность
- •Определение
- •Применение
- •История
3.1.2. Методы уточнения корней нелинейных уравнений
Одним из методов уточнения корня на отрезке является метод половинного деления (метод дихотомии).
Метод половинного деления. Для уточнения корня нелинейного уравнения (3.1) на отрезке , где , а производная сохраняет знак, разделим отрезок пополам и исследуем знак функции в полученной точке , где . Из двух отрезков и выберем тот, на котором функция меняет знак.
Уменьшая новый отрезок в два раза, повторяем процесс и т. д. Получим последовательность вложенных отрезков
на концах которых выполняется неравенство ,
где . (3.2)
Последовательность является монотонной неубывающей ограниченной последовательностью, а последовательность − монотонной невозрастающей ограниченной последовательностью. Значит, существует предел
.
Тогда .
Оценку погрешности решения на -м шаге вычислений можно получить из соотношения (3.2) в виде
(3.3)
Здесь с точностью не превышающей .
Пример. Методом половинного деления с точностью найдём корень уравнения при
Решение. Выше, при отделении корней табличным способом, было установлено, что искомый корень принадлежит отрезку . На каждом шаге вычислений значение корня принимаем равным
С погрешностью
Будем производить вычисления и выбирать последовательность вложенных отрезков используя условие .
Шаг 1.
Так как и то полагаем
Шаг 2.
Так как и то полагаем
Шаг 3.
Так как и то полагаем
Шаг 4.
Так как и то полагаем
Шаг 5.
Так как и то полагаем
Шаг 6.
Так как и то полагаем
Шаг 7.
Так как и то полагаем
Таким образом, заданная точность достигается на седьмом шаге метода половинного деления, поэтому приближённым значением корня с точностью будем считать число
Кроме метода дихотомии для уточнения корня на отрезке применяются итерационные методы.
Метод простых итераций. Пусть известно, что нелинейное уравнение имеет на отрезке единственный действительный корень . Требуется найти этот корень приближённо с заданной точностью . Применяя тождественные преобразования, приведём уравнение к виду
(3.4)
Выберем произвольно приближённое значение корня и вычислим . Найденное значение подставим в правую часть равенства (3.4) и вычислим . Продолжая процесс вычислений дальше, получим числовую последовательность
.
Если существует предел этой последовательности, то он и является корнем уравнения (3.4). В самом деле, пусть
.
Тогда, переходя к пределу в равенстве
и учитывая непрерывность функции на отрезке , получим
или .
Корень можно вычислить с заданной точностью по итерационной формуле
(3.5)
Достаточное условие, при котором итерационный процесс сходится, определяет следующая теорема.
Теорема 3.4. Пусть функция определена и дифференцируема на отрезке , причём все её значения , и выполняется условие
Тогда процесс итераций (3.5) сходится независимо от начального значения и предельное значение является единственным корнем уравнения (3.4) на отрезке . Точка определённая теоремой 3.4, называется неподвижной точкой для уравнения (3.4). Приведём геометрическую интерпретацию метода простых итераций. Для этого построим графики двух функций и в одной системе координат. Абсцисса точки пересечения графиков – корень . Построим итерационный процесс. Зададим и вычислим – первое приближение и – второе приближение. В первом случае (рис. 3.5) процесс – сходящийся (). Во втором случае (рис. 3.6) процесс – расходящийся (). Рассмотрим условия, при которых переход от уравнения (3.1) к эквивалентному виду (3.4) будет сопровождаться сходимостью итерационного процесса (3.5). Выполнение условия сходимости можно добиться с помощью перехода от исходного уравнения к эквивалентному виду следующим образом: умножим обе части уравнения (3.1) на , затем прибавим к обеим частям , тогда
. Обозначим , тогда . |
Константа выбирается так, чтобы выполнялось достаточное условие сходимости итерационного процесса (3.5), т. е.
.
Это условие равносильно неравенствам
,