Дискретно-непрерывная математика (стр. 1 )

Парадигма развития науки

Методологическое обеспечение

А.Е. Кононюк

ДИСКРЕТНО-НЕПРЕРЫВНАЯ МАТЕМАТИКА

Книга 4

Алгебры

(четкие и нечеткие)

Часть 2

Киев

Освіта України 2011

УДК 51 (075.8)

ББК В161.я7

К 213

Рецензент: - д-р техн. наук, проф. (Национальный авиационный университет).

К65 Дискретно-непрерывная математика. Алгебры. К.4.Ч.2.

К.4:"Освіта України", 2011. - 668 с.

ISBN 978-966-7599-50-8

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

В работе излагаются основы теории множеств, отношений, поверхностей, пространств, алгебраических систем, матриц, графов, математической логики, теории формальных грамматик и автоматов, теории алгоритмов, которые в совокупности образуют единную методолгически взамосвязанную математическую систему «Дискретно-непрерывная математика».

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

ББК В161.я7

ISBN 978-966-7599-50-8 ©А. Е. Кононюк, 2011

Оглавление

Модуль 4. Методы индукции и признаки делимости……………….5

Микромодуль 14. Методы индукции…………………………………5

Микромодуль 15. Признаки делимости……………………………. 53

Модуль 5. Элементы комбинаторики...…………………………..134

Микромодуль 16. Основные принципы комбинаторики...………135

Микромодуль 17. Методы комбинаторики...………………… ….174

Микромодуль 18. Алгоритмы комбинаторики...………………….203

Микромодуль 19. Методы отсеивания вариантов...………… …..251

Микромодуль 20. Комбинаторика и нечеткие структуры...…… .290

Модуль 6. Алгебра структурных чисел…………………………. 308

Микромодуль 21. Введение в структурные числа………………..308

Микромодуль 22. Структурные числа высшей категории ………337

Модуль 7. Введение в интервальную алгебру……………………360

Микромодуль 23. Вещественная интервальная арифметика…….362

Микромодуль 24. Интервальное оценивание……………………..378

Микромодуль 25. Машинная и комплексная интервальная арифметика……………………………………………………………397

Модуль 8. Методы локализации……………………………………420

Микромодуль 26. Локализация нулей функций одной

вещественной переменной …………………………………………..420

Микромодуль 27. Методы одновременной локализации вещественных корней многочленов………………………………….455

Микромодуль 28. Методы одновременной локализации

комплексных корней многочленов………………………………….467

Микромодуль 29. Операции над интервальными матрицами…….472

Модуль 9. Интервальная арифметика для решения систем

уравнений…………………………………………………………… 484

Микромодуль 30. Итерационная локализация неподвижной

точки для систем нелинейных уравнений………………………… 484

Микромодуль 31. Системы линейных уравнений, поддающиеся методу итерации……………………………………………………. 495

Микромодуль 32. Методы релаксации…………………………… 512

Микромодуль 33. Оптимальность симметрического короткошагового метода со взятием пересечения на каждом шаге………………… 519

Микромодуль 34. О применимости метода Гаусса к системам уравнений с интервальными коэффициентами………………….. 531

Микромодуль 35. Метод и процедура Хансена………………… 545

Микромодуль 36. Итерационные методы для локализации обратной матрицы и разложения на треугольные……………………………. 556

Модуль 10. Методы Ньютоновского типа………………………….575

Микромодуль 37. Методы Ньютоновского типа для системы нелинейных уравнений………………………………………………...575

Микромодуль 38. Методы Ньютоновского типа не использующие обращения матриц ……………………………………………………..611

Микромодуль 39. Методы Ньютоновского типа для частных типов систем нелинейных уравнений………………………………………...616

Микромодуль 40. Полношаговые и короткошаговые методы Ньютоновского типа……………………………………………………629

Приложения…………………………………………………………….638

Список литературы...…………………………………………..........665

Модуль 4.

Методы индукции и признаки делимости

Микромодуль 14.

Методы индукции

4.1. Ведение в методы индукции

Утверждения подразделяются на общие и частные.

Приведем примеры общих утверждений.

Все граждане Украины имеют право на образование.

Во всяком параллелограмме диагонали в точке пере­сечения делятся пополам.

Все числа оканчивающиеся нулем, делятся на 5.

Соответствующими примерами частных утверждений являются следующие:

- Петров имеет право на образование;

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

- 140 делится на 5.

Переход от общих утверждений к частным называется дедукцией Рассмотрим пример.

Все граждане Украины имеют право на образование. (1)

Петров — гражданин Украины. (2)

Петров имеет право на образование. (3)

Из общего утверждения (1) при помощи утверждения (2) получено частное утверждение (3).

Переход от частных утверждений к общим называется индукцией. Индукция может привести как к верным, так и к неверным выводам. Поясним это двумя примерами:

140 делится на 5. (4)

Все числа оканчивающиеся нулем, делятся на 5 (5)

Из частного утверждения (4) получено ообщее утвержде­ние (5) Утверждение (5) верно.

140 делится на 5. (6)

Все трехзначные числа делятся на 5. (7)

Из частного утверждения (6) получено общее утвержде­ние (7). Утверждение (7) неверно.

Спрашивается, как пользоваться в математике индукцией, чтобы получать толъко верные выводы? Ответ на этот вопрос и дается о этом микромодуле.

1. Рассмотрим сначала два примера индукции, недопу­стимой в математике.

Пример 1. Пусть

Легко проверить, что

На основании полеченных результатов утверждаем, что при всяком натуральном п

Пример 2. Рассмотрим трехчлен х2 + х + 41, на кото­рый обратил внимание еще Л. Эйлер. Подставим в этот трехчлен вместо х нуль, получим простое число 41. Под­ставим теперь в этот же трехчлен вместо х единицу, получим опять простое число 43. Продолжая подставлять в трех­член вместо х последовательно 2, 3, 4, 5, 6, 7, 8, 9, 10, получаем всякий раз простое число 47, 53, 61, 71, 83, 97, 113, 131, 151. На основании полученных результа­тов утверждаем, чго при подстановке в трехчлен вместо х любого целого неотрицательного числа всегда в ре­зультате получается простое число.

Почему рассуждения, приведенные в этих примерах, не­допустимы в математике? В чем порочность выводов, которые нами сделаны?

Дело в том, что в обоих этих рассуждениях мы высказали общее утверждение относительно любого (во втором примере относительно любого х) только на основании того, что это утверждение оказалось справедливым для не­которых значений п (или х).

Индукция широко применяется в математике, но при­менять ее надо умело. При легкомысленном же отношении к индукции можно получить неверные выводы.

Так, если в примере 1 сделанное нами общее утвержде­ние случайно оказывается верным, как это доказано ниже в примере 4, то в примере 2 наше общее утверждение оказачось неверным.

В самом деле, при более внимательном изучении трех­члена х2+х+41 обнаружили, что он равен простому числу при х = 0, 1, 2, ..., 39, но при х = 40 этот трех­член равен 412, т. е. числу составному (и уж совсем сразу бросается в глаза, что при х=41 х2+ х + 41 =412 + 41 + 41 делится на 41)).

2. В примере 2 мы встретились с утверждением, спра­ведливым в 40 частных случаях и все же вообще оказавшимся несправедливым.

Приведем еще несколько примеров утверждений, которые справедливы в нескольких частных случаях, а вообще не­справедливы.

Пример 3. Двучлен хп—1, где п — натуральное число, представляет для математиков большой интерес. Достаточно сказать, что он тесно связан с геометрической задачей о делении окружности на п равных частей. Неудивительно по­этому, что двучлен этот всесторонне изучается в математике. Математиков, в частности, интересовал вопрос о разложении этого двучлена на множители с целыми коэффициентами.

Рассматривая эти разложения при многих частных значе­ниях п, математики наблюдали, что все коэффициенты раз­ложения по абсолютной величине своей не превосходят еди­ницы. В самом деле,

Были составлены таблицы, в пределах которых коэффи­циенты этим свойством обладали. Попытки доказать этот факт для всякое п успеха не имели.

В 1938 г. в журнале «Успехи математических наук» (вып. IV) была опубликована заметка выдающегося русского математика , в которой он предложил нашим математикам выяснить этот вопрос.

Эту задачу в 1941 г. решил В. Иванов. Оказалось, что указан­ным свойством обладают все двучлены хп— 1, степень кото­рых меньше 105. Одним же из множителей х105— 1 является многочлен

уже не обладающий этим свойством.

Пример 4. Рассмотрим числа вида +1. При п = 0, 1, 2, 3, 4 числа +1 =3, +1= 5. +1= 17, +1=257. +1=65 537 — простые. Замечательный французский математик XVII в П. Ферма предполагал, что все числа такого вида — простые. Однако в XVIII в. Л. Эйлер нашел, что