Vecka 3, FÖ 5, 2003-04

AMBS och 54.1 – 12

54.1 Vector-valued function

f : ℝ^{n} → ℝ^{m} y = f(x), x ∈ ℝ, y ∈ ℝ^{m} column vecors Caucy sequence in ℝ^{n}, {x^{(j)}}_{j=1}^{∞},

∥x^{(i)} − x^{(j)}∥ → 0 as i, j → ∞  (1)

Here ∥x∥ = \sqrt{∑{n \atop k=1}}x_{k}^{2} so that (1) means

∑_{k=1}^{n}(x_{k}^{(i)} − x_{k}^{(j)})^{2} → 0

which implies

x_{k}^{(i)} − x_{k}^{(j)} → 0, k = 1, …, n

so that x_{j}^{(i)}k is a Cauchy-sequence of real numbers. Hence there is x_{k} ∈ ℝ such that

x_{k}^{j} → x_{k}, k = 1, …, n

and then, with x = [ \begin{matrix}x_{1} \\ x_{k} \end{matrix} ],

∥x^{(j)} − x∥ = \sqrt{∑_{k=1}^{n}(x_{k}^{(j)} − x_{k})^{2}} → 0, j → ∞.

Therefore: every Caucy sequence {x^{(j)}}_{j=1}^{∞} in ℝ^{n} has a limit x ∈ ℝ^{n}.

Example: x^{(j)} = [ \begin{matrix}1 + y_{j} \\ e^{−j} \end{matrix} ] ∈ ℝ^{2}

∥x^{(i)} − x^{(j)}∥^{2} = ((1 + \frac{1}{i}) − (1 + \frac{1}{j}))^{2} + (e^{−i} − e^{−j})^{2}

= (\frac{1}{i} − \frac{1}{j})^{2}(e^{−i} − e^{−j})^{2}

= (\frac{1}{i} \underbrace{(1 − \frac{i}{j})}_{≤1} )^{2} + (e^{−i} \underbrace{(1 − e^{i−j})}_{≤1} )^{2}

≤ \frac{1}{i^{2}} + e^{+2i} → 0 as j ≥ i, i → ∞.

Thus x^{j} is a Caucy sequence. Exercise. prove that its limit is x = [ \begin{matrix}1 \\ 0 \end{matrix} ] , i.e., ∥x^{(i)} − x∥ → 0 as k → ∞.

54.2. Curve in ℝ^{n}.

g : I → ℝ^{n} (n ≥ 2) where I = [a, b] is an interval.

x = g(t), t ∈ I

parametrization of the curve. Example: straight line in ℝ^{n}

x = x̄ + tz, t = (−∞, ∞)

Here g(t) = x̄ + tz, z vector of direction.

54.4. Surface in ℝ^{n}, parametrization

\begin{matrix}g : Q ⟶ ℝ^{n} (n ≥ 3) \\ x = g(x) = g(s_{1}, s_{2}), s = [ \begin{matrix}s_{1} \\ s_{2} \end{matrix} ] , s ∈ Q ⊂ ℝ^{2} \end{matrix}

54.5 Sipschitz condition

\begin{matrix}f : ℝ^{n} ⟶ ℝÅm \\ ∥f(x) − f(y)∥ ≤ L_{f}∥x − y∥ \end{matrix}

Important example: linear function

f(x) = Ax, A m × n
∥f(x) − f(y)∥ = ∥Ax − Ay∥ =
= ∥A(x − y)∥ ≤ L_{f}∥x − y∥

It is sufficient to consider z = x − y.

∥AZ∥^{2} =) ∑_{i=1}^{m}((Az)_{i})^{2}

= ∑_{i=1}^{m} ( ∑_{j=1}^{m} a_{ij}z_{j})^{2} ≤ \{Cauchy’s inequality AMBS 42.5\} ≤ ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}^{2} \underbrace{∑_{j=1}^{n} z_{j}^{2}}_{=∥z∥^{2}}

Note: (Az)_{i} the scalar product of z and the i:th row of A.

∥Az∥ ≤ \sqrt{∑_{i=1}^{m} ∑_{j=1}^{n} a?2_{ij}}∥z∥ ∀z ∈ ℝ^{n}.

Hence smallest Lipschitz constant is called the norm of the matrix A, L_{f} = ∥A∥. Hence

∥Ax∥ ≤ ∥A∥∥x∥ forallx ∈ ℝ^{n}

∥A∥ = max_{∥x∥=1} ∥Ax∥

It is difficult to compute ∥A∥ there is no formula. We usually have to be satisfied with an estimate, e.g.

∥A∥ ≤ \sqrt{∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}^{2}}.

54.7 The Chain Rule

\begin{matrix}g : ℝ^{n} → ℝ^{m} \\ f : ℝÅm → ℝ^{p} \end{matrix}

Composite function

\begin{matrix}h = f ∘ g : ℝ^{n} → ℝ^{p}, h(x) = f(g(x)) \\ \underbrace{h′(x)}_{p×n} = \underbrace{f′(g(x))}_{p×m} \underbrace{g′(x)}_{m×n} \end{matrix}

54.8 The mean value theorem

f : ℝ^{n} → ℝ

f′(x) = [\frac{∂f}{∂x_{2}} (x), … \frac{∂f}{∂x_{n}}] = ∇f(x),

h(t) = f(x̄ + t(x − x̄)), t ∈ [0, 1]

= f(g(t)), g′(t) = x − x̄ h : ℝ → ℝ.

Mean-value theorem (AMBS 28.11) for one-variable function: there is t ∈ [0, 1] such that

h(1) − h(0) = h(1 − 0) = h′(t)

But

h(1) = f(x), h(0) = f(x̄)
h′(t) = f′(g(t))g′(t) =
= f′(y)(x − x̄) y = g(t)
= If(y)(x − x̄)

Therefore:

f(x) − f(x̄) = ∇f(y)(x − x̄)

54.9 Direction of steepest descent

f : ℝ^{n} → ℝ

f′(x) = [\frac{∂f}{∂x_{1}} (x), …, \frac{∂f}{∂x_{n}} (x)] = ∇f(x), n × 1

g_{z}(t) = x̄ + tz, ∥z∥ = 1

g′_{z}(t) = z

F_{z}(t) = f(x̄ + tz) = f(g_{z}(t)), F − z(0) = f(x̄)

Chain rule:

\begin{matrix}F′_{z}(t) = f′(g_{z}(t))g′_{z}(t) = ∇f(x̄ + tz)z \\ F′_{z}(0) = ∇f(x̄)z = [\frac{∂f}{∂x_{1}} … \frac{∂f}{∂x_{n}} ] [ z_{1} ; ⋮ ; z_{n} ] \end{matrix}

This is the scalar product of z with the vector f′(x̄)^{T} = If(x̄)^{T}. f(x) is increasing along the line through x̄ in the direction z if F′_{Z}(0) = If(x̄)z > 0. The direction steepest ascent is obtained when z is parallell to ∇f(x̄)^{T}, i.e.,

z = \frac{∇f(x̄)^{T}}{∥∇f(x̄)∥} (normalized)

The direction of steepest descent is the opposite direction

z = −\frac{∇f(x̄)^{T}}{∥∇f(x̄)∥}.

This requires that ∇f(x̄) ≠ 0. We say that f has a local minimum at x̄ if there is a radius ϵ > 0 such that

f(x̄) ≤ f(x) ∀x with ∥x∥ ≤ ϵ

and a local maximum if

f(x̄) ≥ f(x) ∀x with ∥x∥ ≤ ϵ

If local min or max at x̄, then F′_{z}(0) = 0 in all directions z. This means

F′_{z}(0) = ∇f(x̄)z = 0 ∀z

which implies

∇f(x̄) = 0  (2)

If (2) holds then we say that x̄ is a stationary point for f. Thus (2) is a necessary condition for local maximum or minimum. But is not sufficient, e.g., if (2) holds then might also be suddle point, where F_{z}(t) has a maximum at t = 0 for some direction z and minimum for some direction.

More complicated behavior might also occur.

To minimize (or maximize) a function is a very common task. For example, a mechanical system is in stable equilibrium when its energy is minimal. In chemical engineering we want to maximize the yield of a production process while we minimize the cost of production.

We shall learn two methods for finding minima:

1. solve the equations

∇f(x̄) = 0

(by Newton’s method)

2. search for a minimum along the direction fo steepest descent.

Example: The quadratic function

f(x) = x^{T} Ax = [x_{1} x_{2}] [ \begin{matrix}2 & 1 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}x_{1} \\ x_{2} \end{matrix} ] =

= 2x_{1}^{2} + 2x_{1}x_{2} + 2x_{2}^{2}

f′(x) = [4x_{1}^{2} + 2x_{2}, 2x_{1} + 4x_{2}^{2}]

= 2 [ \begin{matrix}2 & 1 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}x_{1} \\ x_{2} \end{matrix} ] = 2Ax

f′(x) = 0 means

\{ \begin{matrix}2x_{1} + x_{2} = 0 \\ x_{1} + 2x_{2} = 0 \end{matrix}

with unique solution x = 0.

Take x = [ \begin{matrix}1 \\ 0 \end{matrix} ]. The direction of steepest descent is

\begin{matrix}z = −\frac{f′(x)^{T}}{∥f′(x)∥} = −\frac{1}{\sqrt{2}} [ \begin{matrix}2 \\ 1 \end{matrix} ] \\ f(x) = f(1, 0) = 2 \end{matrix}