Herkese merhaba,
Daha önce sevgili @coderistan , Sayısal Yöntemler dersinde anlatılan yöntemlerle ilgili bir görsel paylaşmıştı.
Görselde yer alan yöntemlerden ilki olan Newton-Raphson yöntemi ile ilgili bir örnek yapalım isterim.
Bu yöntem, lineer olmayan bir f(x) fonksiyonunun 0’a eşit olduğu yere, Taylor Serilerini kullanarak yakınsamaya çalışan bir yöntemdir.
Yöntem şöyle çalışıyor:
f(x)'in 0’a yaklaşabilmesi için bir başlangıç değeri seçiyoruz. Başlangıç değeri complex tipte bir sayı. Neden complex? Çünkü, denklemin reel kökleri olmayabilir.
Burada, her başlangıç değeri, f(x) = 0’a yaklaşmayı sağlamayabilir. Başlangıç değerlerini öyle bir şekilde seçmemiz lazım ki, fonksiyonun kökleri daha isabetli bir şekilde hesaplanabilsin.
Kompleks sayılar için en uygun başlangıç değerleri, bu sayılar bir çemberin kökleriyle ilgili oldukları için; çember üzerinde eşit bir şekilde dağılmış noktalar olarak seçilir. Bu seçimde, elbette cos ve sin fonksiyonlarını kullanmamız gerekiyor.
Kök sayısı, denklemin derece sayısına bağlı bir kavramdır. 3. dereceden denklemin toplamda 3 kökü, 4 katsayısı vardır.
Yani eğer denklemde 3 kök varsa, bu kökleri bulmak için başlangıç değerleri şöyle oluşturulabilir:
from math import pi, cos, sin
n = 3
roots = [complex(cos(2 * pi * i / n), sin(2 * pi * i / n) for i in range(n)]
print(roots)
Newton-Rhapson yöntemi, f(x) fonksiyonunun mevcut eğimi boyunca sürekli türevinin alınarak, türevin 0’a yaklaştığı yeri bulmaya çalışır.
Türev fonksiyonunu şöyle yazabiliriz:
def derivate(
x: complex,
n: int,
coef: list[float],
h: float = 1e-5
) -> complex:
return (func(x + h, n, coef) - func(x, n, coef)) / h
Newton-Rhapson yöntemi ise şöyle yazılabilir:
def newton_rhapson_method(
n: int,
coef: list[float],
roots: list[complex],
max_step: int,
tolerance: float
) -> None:
for i in range(n):
x = complex(cos(2 * pi * i / n), sin(2 * pi * i / n))
for step in range(max_step):
x = x - func(x, n, coef) / derivate(x, n, coef)
if abs(func(x, n, coef)) < tolerance:
break
roots[i] = x
Bu fonksiyonları oluşturduktan sonra, katsayılara göre değişecek olan denklem fonksiyonunu tanımlayalım:
def func(x: complex, n: int, coef: list[float]) -> complex:
total = complex(0, 0)
for i in range(n + 1):
total += coef[i] * x ** (n - i)
return total
Buradaki func fonksiyonu, köklerini bulmaya çalıştığımız fonksiyonu üretir ve bu fonksiyonu karmaşık tipte olan x değerleri ile çalıştırır.
Şimdi, main fonksiyonunu tanımlayabiliriz:
def main():
coef = [1, -1, -1]
n = len(coef) - 1
roots = [complex(0, 0)] * n
newton_rhapson_method(n, coef, roots, 100, 1e-7)
for i in range(n):
print(f"{roots[i].real} + {roots[i].imag}j")
if __name__ == "__main__":
main()
Yukarıda coef isimli değişken, 2. dereceden bir denklem olan Fibonacci Serisi fonksiyonunun katsayıları olan 1, -1, -1 değelerini içeren katsayı listesidir.
Fibonacci fonksiyonunun denklemi::
Gördüğünüz gibi, bu denklemin katsayıları [1, -1, -1].
Fibonacci fonksiyonu ile alakalı olarak aşağıdaki başlığı da incelemenizi tavsiye ederim:
Yukarıdaki başlıkta fibonacci fonksiyonunun kökleri şöyle bulunmuştu:
kok1 = 1.618033988749895
kok2 = -0.6180339887498949
Yukarıdaki Newton-Rhapson metodu ise kökleri aşağıdaki gibi bulur:
kok1 = 1.618033988752065 + 0.0j
kok2 = -0.6180339887479553 + -4.067290634408824e-27j
Ondalık kısımda farklılıklar olması beklenen bir durumdur.
Newton-Raphson yöntemi, bir fonksiyonun kökünü bulmak için, başlangıç değeri kullanır ve yinelemeli (iteratif) bir yaklaşım yapılır. Bu yaklaşım, her adımda fonksiyonun türevini kullanarak köke daha yakın bir noktaya yaklaşılmasını sağlar.
Diğer yandan, Durand-Kerner yönteminde, başlangıç değerleri seçilmez; polinomun katsayıları kullanılarak bir companion matrix (kompanyon/refakatçı matris) oluşturulur. Bu matrisin özdeğerleri hesaplanarak, polinomun kökleri bulunur. Özdeğerler, matrisin karakteristik özelliklerini gösteren ve polinomun köklerine karşılık gelen değerlerdir. Bu yaklaşımda, kökler doğrudan kompanyon matrisin özdeğerlerinden elde edilir.
Durand-Kerner yöntemi, Newton-Raphson yöntemine kıyasla, özellikle polinomların köklerini aynı anda ve daha isabetli bir şekilde bulması açısından avantajlıdır.
Durand-Kerner yöntemi ile alakalı olarak aşağıdaki linkleri de inceleyebilirsiniz:
Durand-Kerner Yöntemi:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def dot_product(n: int, v1: list[complex], v2: list[complex]) -> complex:
result = complex(0, 0)
for i in range(n):
result += v1[i] * v2[i]
return result
def scalar_multiply(
n: int,
scalar: complex,
vector: list[complex],
multiplied: list[complex]
) -> None:
for i in range(n):
multiplied[i] = scalar * vector[i]
def vector_subtract(
n: int,
v1: list[complex],
v2: list[complex],
subtracted: list[complex]
) -> None:
for i in range(n):
subtracted[i] = v1[i] - v2[i]
def gram_schmidt(
n: int,
A: list[list[complex]],
Q: list[list[complex]],
R: list[list[complex]],
) -> None:
for i in range(n):
v = [complex(0, 0)] * n
for j in range(n):
v[j] = A[j][i]
for j in range(i):
R[j][i] = dot_product(n, Q[j], v)
multiplied = [complex(0, 0)] * n
scalar_multiply(n, R[j][i], Q[j], multiplied)
subtracted = [complex(0, 0)] * n
vector_subtract(n, v, multiplied, subtracted)
for k in range(n):
v[k] = subtracted[k]
R[i][i] = dot_product(n, v, v) ** .5
for j in range(n):
Q[i][j] = v[j] / R[i][i]
def qr_algorithm(
n: int,
roots: list[complex],
companion: list[list[float]],
A: list[list[complex]],
Q: list[list[complex]],
R: list[list[complex]],
max_step: int,
tolerance: float
) -> None:
for i in range(n):
for j in range(n):
A[i][j] = complex(0, companion[i][j])
for step in range(max_step):
for i in range(n):
for j in range(n):
Q[i][j] = complex(0, 0)
R[i][j] = complex(0, 0)
gram_schmidt(n, A, Q, R)
for i in range(n):
for j in range(n):
total = complex(0, 0)
for k in range(n):
total += R[i][k] * Q[k][j]
A[i][j] = total
converged = 1
for i in range(1, n):
for j in range(i):
if abs(A[i][j]) >= tolerance:
converged = 0
break
if not converged:
break
if converged:
break
for i in range(n):
roots[i] = A[i][i]
def companion_matrix(
n: int,
coef: list[float],
companion: list[list[float]]
) -> None:
for i in range(n):
for j in range(n):
if not j:
companion[i][j] = -1.0 * coef[i + 1] / coef[0]
elif i + 1 == j:
companion[i][j] = 1
def func(x: complex, n: int, coef: list[float]) -> complex:
total = complex(0, 0)
for i in range(n + 1):
total += coef[i] * x ** (n - i)
return total
def durand_kerner_method(
n: int,
coef: list[float],
roots: list[complex],
max_step: int,
tolerance: float
):
companion = [[0] * n for _ in range(n)]
companion_matrix(n, coef, companion)
A = [[complex(0, 0)] * n for _ in range(n)]
Q = [[complex(0, 0)] * n for _ in range(n)]
R = [[complex(0, 0)] * n for _ in range(n)]
qr_algorithm(n, roots, companion, A, Q, R, max_step, tolerance)
for i in range(n):
for step in range(max_step):
denominator = complex(1, 0)
for j in range(n):
if i != j:
denominator *= roots[i] - roots[j]
roots[i] = roots[i] - func(roots[i], n, coef) / denominator
if abs(func(roots[i], n, coef)) < tolerance:
break
def main():
coef = [1, -1, -1]
n = len(coef) - 1
roots = [complex(0, 0)] * n
durand_kerner_method(n, coef, roots, 100, 1e-7)
for i in range(n):
print(f"{roots[i].real} + {roots[i].imag}j")
if __name__ == "__main__":
main()