Lecture 24

Question 1

Jacobian matrix

Answer 1

Given n functions, Jf(x)

[[∂f1/∂x1, …, ∂f1/∂xn], …, [∂fn/dx1, …, ∂fn/∂xn]]

Question 2

Newton’s method multi-dimensional update

Answer 2

xk+1 = xk + sk
solve Jk.sk = -f(xk)
(sk = - Jf(xk)^{-1}.f(xk))

Question 3

Newton’s method multi-dimensional Python

Answer 3

import scipy.optimize as opt

def f(xvec):
    x, y = xvec
    return np.array([
        x + 2*y - 2,
        x**2 + 4*y**2 - 4
    ])

def Jf(xvec):
    x, y = xvec
    return np.array([
        [1, 2],
        [2*x, 8*y]
    ])

sol = opt.root(f, x0=[1, 1], jac=Jf)
root = sol.x

Question 4

Cost Newton’s method multi-dimensional

Answer 4

Solve jacobian: Factorization O(n^3)…

could be cheaper if matrix is sparse

Question 5

Secant method multi-dimensional

Answer 5

Approximate Jacobian ~Jk+1(xk+1 - xk) = f(xk+1) - f(x)

n^2 unknowns, n equations (solution not unique)

Question 6

Broyden’s method

Answer 6

Find an approximate for the jacobin matrix:
min ||Bk+1 - Bk|| s.t. Bk+1 s.t Bk+1(xk+1 - xk) = f(xk+1) - f(x)

• x0 initial guess, B0 initial guess (J0 or I)
• Solve Bk.sk = -f(xk) O(n^3)
• update xk+1=xk+sk
• evaluate dfk+1 = f(xk+1)-f(xk)
• update Bk+1 = Bk + (dfk+1 - Bk.sk)@sk.T / sk.T@sk