Чисельне інтегрування функції методом Ромберга

Перш ніж приступити до розгляду чергового методу чисельного інтегрування, нагадаємо, що інтеграл від функції чисельно дорівнює площі криволінійної трапеції, обмеженої графіком цієї функції і межами інтегрування . Відмітимо, що розглядувані на даному сайті методи (метод прямокутниківметод трапецій, метод Сімпсона), базуються на процедурі поділу відрізка  на елементарних частин, після чого, площа криволінійної трапеції обчислюється, як сума площ  прямокутників чи трапецеїдних фігур (в залежності від вибраного методу). Проте, результат отриманий згідно даних методів, сильно залежить від величини кроку (), що позначається на точності обчислення визначеного інтеграла особливо в тих випадках, коли функція має немонотонний характер.

Використання екстраполяції Річардсона, при інтегруванні відомими методами, дозволяє значно скоротити машинний час при незмінній точності результату (оскільки уточнення результату інтегрування не потребує додаткових обчислень функції). Застосування наведеної нижче методики до ітераційної формули трапецій складає розглядуваний метод Ромберга.

Далі, розглянемо основну суть екстраполяції Річардсона. Для цього, вибиремо деякий крок  і розрахуємо по формулі трапецій деяке значення інтеграла . Далі, крок  зменшимо удвічі, в результаті чого, отримаємо нове значення . Тоді, згідно з екстраполяцією Річардсона, розраховане значення інтеграла може бути уточнене за формулою:

Читати повністю

Побудова мінімального кістятка за алгоритмом Борувки в середовищі програмування delphi

Програма реалізує процес побудови дерева мінімальної вартості в неорієнтованому графі і використовує для цього алгоритм Борувки. Відмітимо, що детально розглядати теоретичну частину даного алгоритму не будемо, її можна знайти за посиланням побудова мінімального кістятка за алгоритмом Борувки, а перейдемо до розгляду основних елементів головної форми delphi-проекту.

Отже, головна форма складається з панелі інструментів, області графічного представлення, області, яка містить матрицю суміжності графа та області виводу результатів. Розглянемо кожну з них більш детально.

Читати повністю

Побудова мінімального кістяка в неорієнтованому графі використовуючи алгоритм Борувки

Алгоритм Борувки, як і алгоритм Крускала та алгоритм Прима, призначений для відшукання дерева мінімальної вартості в неорієнтованому графі. Основна ідея даного алгоритму дещо подібна до першого, тобто пошук мінімального кістяка також починається з розгляду дерев, кожне з яких складається з однієї вершин. Після чого, з допомогою ітераційного процесу, відбувається обєднання найближчих дерев і продовжується даний процес до тих пір, поки всі об'єкти не належатимуть одному дереву. Відмітимо, що характерною особливістю алгоритму Буровки є те, що на кожній такій ітерації кількість дерев скорочується мінімум в два рази.

Ілюстрація роботи алгоритму Борувки

Ілюстрація роботи алгоритму Борувки

Далі більш детально зупинемося на розгляді ітераційного процесу, тобто розглянемо, яким чином в алгоритмі Борувки відбувається пошуку найближчих дерев. Отже, нехай на деякій ітерації, для заданого дерева, потрібно знайти найближче до нього. Для цього необхідно для кожної компоненти вихідного дерева (на малюнку зображені у вигляді кола з штрихпунтирною лінією) знайти найближчу компоненту з іншого дерева. Далі з усіх знайдених елементів вибрати мінімальний, який і стане ребром, що обєднює два дерева.

Читати повністю