$f(x,y)$ is a surface (3D). So is $g(x,y)$.
* They will intersect in a curve.
$$g(x,y) \approx g(x_0,y_0) + \left.\frac{\partial g}{\partial x}\right|_{x_0,y_0}\delta x + \left.\frac{\partial g}{\partial y}\right|_{x_0,y_0}\delta y,$$ where $\delta x = (x-x_0)$, and similar for $\delta y$.
Or, rearranging: $$[J](\boldsymbol{\delta x}) = -(\boldsymbol{f}(\boldsymbol{x}_0)),$$ where bold symbols denote vector quantities: the elements of $\boldsymbol{\delta x}$ are $\delta x$ and $\delta y$, etc.
function newton1D(x, f, dfdx, tol, maxit=100)
for it in 1:maxit
xnew = x - f(x)/dfdx(x)
if abs((xnew-x)/xnew) <= tol
return xnew,it+1
end
x = xnew
if it == maxit
println("Warning, no convergence in $maxit iterations")
return xnew,it+1
end
end
end;
import LinearAlgebra: norm
function multiNewt(f, Jac, x, tol, maxit=100)
for it in 1:maxit
fvec = f(x)
J = Jac(x)
xnew = x - J\fvec
if norm(xnew-x)/norm(xnew) <= tol
return xnew,it+1
end
x = xnew
if it == maxit
println("Warning, no convergence in $maxit iterations")
return xnew,it+1
end
end
end;
Solve:
$$f(x,y) = x^2 + y^2 - 3 = 0,$$$$g(x,y) = 2y - x^2 = 0.$$fg(x) = [ x[1]^2 + x[2]^2 - 3,
2*x[2] - x[1]^2 ]
Jac(x) = [ 2*x[1] 2*x[2];
-2*x[1] 2.0 ];
x0 = [10, 10]
x_solution,nit = multiNewt(fg, Jac, x0, 1.E-6)
println("solution: $x_solution")
println("f(x): $fg(x_solution)")
solution: [1.414213562373095, 1.0] f(x): fg(x_solution)
KERNEL EXCEPTION KeyError: key "debug_request" not found Stacktrace: [1] getindex(h::Dict{String, Function}, key::String) @ Base ./dict.jl:498 [2] eventloop(socket::ZMQ.Socket) @ IJulia ~/.julia/packages/IJulia/6TIq1/src/eventloop.jl:8 [3] (::IJulia.var"#14#17")() @ IJulia ./task.jl:484
If the derivative of $f(x)$ is unknown, or inconvenient, a numerical derivative can be used:
$$f^{\prime}(x)\approx\frac{f(x+\Delta x)-f(x)}{\Delta x},$$$$\Delta x = \sqrt{\epsilon_{mach}}\;|x| = 10^{-8}|x|.$$The second expression is an optimized value for $\Delta x$. See N.R. section 5.7, p. 229, 3rd edition for details.
Method | Notes | Convergence | Order | Comments |
---|---|---|---|---|
Bisection | simple, brackets root, slow | robust | 1 | good for finding a root, refine with an open method |
Regula Falsi | brackets root, linear interpolation | robust | >1 | faster than bisection |
Fixed Point | $x=g(x)$, no unique form, but easy | inconsistent | 1 | easy to use but unreliable |
Newton's | analytic or numerical derivatives | converges close to root | 2 | widely used, needs a good starting point |
secant | Like Regula Falsi, use last 2 points | may not converge | 1.62 | recommended when no analytic derivative |
Muller's | like Secant, but 3 pt interpolant | may not converge | 1.84 | not as common, use Newton or Secant |
Brents's | combo of bracketing, bisection, interpolation | robust | -- | recommended by N.R. |