Wednesday, June 26, 2013

Related Rates

Related rates is just an application of the chain rule. Typically, we have a function $y = x$, where $x$ is implicitly dependent on another variable, usually time, $t$. Thus, if we differentiate the equation with respect to time, we have $\frac{dy}{dt} = \frac{dy}{dx}\frac{dx}{dt}$. Related rates problems usually give su two of these differentials, and ask us to compute the third.

Example 1

Taken from practice exercise in Cracking the GRE Mathematics Subject Test, 4th Edition

The radius of a circle is decreasing at a rate of $0.5$ cm per second. At what rate in cm2/sec is the circle's area decreasing when the radius is $4$ cm?

The area of the circle is given by $A = \pi r^2$. Differentiating with respect to time, $t$, we have

\[ \frac{dA}{dt} = 2\pi r \frac{dr}{dt} \]

We are given that $\frac{dr}{dt} = -0.5$, and that, at the refrence time $t_0$, the radius is $4$. Plugging these values in, we have

\[ \frac{dA}{dt} = 2 \pi (4) (-0.5) = -4 \pi \]

Thus, the area is decreasing by $-4\pi$ cm2/sec.

Example 2

Taken from practice exercise in Calculus with Analytic Geometry, Third Edition

A board 5 feet long slides down a wall. At the instant the bottom end is 4 feet from the wall, the other end is moving down the wall at the rate of 2 feet per second. At that moment, how fast is the bottom end sliding along the ground?

If we let $y$ denote the height of the board against the wall, and $x$ the distance of the board from the wall, then we have the equation

\[ 5^2 = x^2 + y ^2 \]

Differentiating with respect to time, we have

\[ 0 = 2x\frac{dx}{dt} + 2y \frac{dy}{dt} \]

We are given that, at the reference time, $t_0$, $\frac{dx}{dy} = -2$ and $x = 4$. Since, $x = 4$, we know that $y=3$ (it's a 3-4-5 triangle). Plugging these values into the above equation, we have

\[ 0 = 2(4)\frac{dx}{dt} + 2(3)(-2) \]

Which gives us $\frac{dx}{dt} = \frac{3}{2}$. Thus, the bottom of the board is sliding at a rate of 1.5 feet per second.

Monday, June 24, 2013

The Newton-Raphson Method

The Newton-Raphson method (often shorted to Newton's method) is an algorithm for approximating the roots of a real-valued function.

The method is quite simple, relying upon successive tangent line approximations. Let $d$ be a zero of the function $f$, and assume that $f$ is differentiable on an open interval containing $d$. Pick a value $c_0$ that is believed to be close to $d$, compute the tangent line approximation at $c_0$, and compute the root of this tangent line. Call the root $c_1$. $c_1$ is our new approximation for $d$. Again, we determine the tangent line approximation for $c_1$, and compute the root of this tangent line, calling it $c_2$. We stop when $c_{i+1} - c_i < \epsilon$, where $\epsilon$ is a small value representing how close we would like our approximation to be to $d$.

There are two conditions to watch out for. First, if $f(c_i) = 0$, we have found a zero, and are done. Second, if the tangent line approximation for $c_i$ is horizontal (e.g., 0 slope), we are done; Newton's method is unable to determine the root. In such a case, we might try a different starting guess for $c_0$, and see if we have better luck.

Also, note that the tangent line approximation to $f$ at $c_i$ is given by

\[ y = f(c_i) + f'(c_i)(x - c_i) \]

Since we are interested in the root of this line, we set $y = 0$, and solve for $x$, giving

\[ \frac{-f(c_i)}{f'(c_i)} + c_i = x \]

Call this formula $r(c)$. Our steps for finding the root of $f$ are thus

  1. If $f(c_i)$, STOP. $c_i$ is the root. Otherwise, GOTO STEP 2.
  2. if $f'(c_i) = 0$, STOP. Start over, trying a different value for $c_0$.
  3. $c_{i+1} = r(c_i)$. If $|c_{i+1} - c_i| < \epsilon$, STOP. $c_{i+1}$ is a good approximation to the root, $d$, of $f$.
  4. $c_i = c_{i+1}$. GOTO STEP 1.

Example

Find the root of the polynomial $f(x) = x^3 - 2x - 5$ in the interval $[0, 3]$.

First since $f$ is negative at $0$ and positive at $3$, we know by the Intermediate Value Theorem that a zero exists in this interval. The derivative of $f$ is $3x^2 - 2$, and the root of the tangent line approximation of $f$ at $x$ is given by \[ r(x) = \frac{-f(x)}{f'(x)} + x \]

If we choose $x=1$ as our initial guess, we have that

$c$$f(c)$$f'(c)$$n(c)$
1-617
73241454.7655
4.765593.69366.1303.3487
3.3487 25.85431.6412.5316
2.53166.161817.2272.1739
2.17390.9257112.1782.0979
2.09790.03744511.2042.0946
2.0946 5.4155e-0411.1622.0946

Thus, $2.0926$ is a zero to $f$.

Linear Approximations Using Differentials

If $f$ is a continuous function such that $f'(a) \ne 0$, then the tangent line to the curve $y = f(x)$ at $a$ provides a good approximation of the graph of $f$ near $x = a$. Recall that the tangent line at $a$ is given by

\[ y = f(a) + f'(a)(x-a) \] Instead of using the tangent line for the approximation, an equivalent formulation of the approximation would appeal directly to the definition of the derivative. That is, since \[ f'(a) = \lim_{x \to a} \frac{f(x) - f(a)}{x - a} \] then for values $x$ close to $a$, we have that \[ f(x) \approx f'(a)(x - a) + f(a) \] If we subtract both sides by $f(a)$, then we arrive at \[ f(x) - (fa) \approx f'(a)(x-a) \] which can formulated in terms of the differentials \[ \Delta f \approx f'(a) \Delta x \]

Example

As an example, let's approximate the value of $\sqrt[3]{1.1}$.

We note that 1.1 is close to 1. Thus, we will make an approximation for $\sqrt[3]{1.1}$ based on the tangent line to the curve at $x=1$.

Since the derivative of $\sqrt[3]{x}$ is $\frac{1}{3 x^{2/3}}$ we have that the tangent line to curve at $x=1$ is \[ y = 1 + \frac{1}{3}(x - 1) \] Thus, substituting $1.1$ for $x$, we have as our approximation \[ y = 1 + \frac{1}{3} \frac{1}{10} = \frac{31}{30} \] It turns out that is approximation is quite good, as by calculator we can see that \[ \frac{31}{30} - \sqrt[3]{1.1} \approx 1.033333 - 1.032280 = 0.001053 \]

Sunday, June 23, 2013

Calculus I - The Derivative

Definition

For a real-valued function $f$ of a single real variable, the derivative of $f$ is the function $f'$ whose value at $x$ is

\[ f'(x) = \lim_{h \to 0} \frac{f(x +h) - f(x)}{h} \]

if this limit exists. Geometrically, the derivative is the slope of the secant line beween the points $(x, f(x))$ and $(x + h, f(x + h))$. As $h \to 0$, this secant line becomes tangent to the graph of $f$ at the point $(x, f(x))$.

Computing the Derivative By Hand

Although students usually end up memorizing the derivatives for standard, common functions, it is instructive to understand that the derivative can be computed directly from the definition. As an example, let's compute the derivative of $x^3$.

\[ f'(x) \]=\[ \lim_{h \to 0} \frac{f(x + h) - f(x)}{h} \]
=\[ \lim_{h \to 0} \frac{(x+h)^3 - x^3}{h} \]
=\[ \lim_{h \to 0} \frac{x^3 +3x^2h + 3xh^2 + h^3 - x^3}{h} \]
=\[ \lim_{h \to 0} \frac{3xh(x + h) + h^3}{h} \]
=\[ \lim_{h \to 0} 3x(x+h) + h^2 \]
=\[ 3x^2 \]

Alternative Notations

The Leibniz notation, $\frac{df}{dx}$ is sometimes used instead of the prime notation to denote the derivate of $f$ with respect to $x$. More specifically, $\frac{d}{dx}$ is thought of as the differentiation operator that is applied to the function $f$.

General Rules

The following rules aid in calculating derivatives:

Sum

\[ (f + g)'(x) = f'(x) + g'(x) \]

Scalar Multiplier

\[ (kf)'(x) = kf'(x) \mbox{, where $k$ is a constant} \]

Product

\[ (fg)'(x) = f(x)g'(x) + f'(x)g(x) \]

Quotient

\[ \frac{f}{g}'(x) = \frac{g(x)f'(x) - f(x)g'(x)}{g(x)^2} \]

Differentials

In Leibniz notation, the chain rule is

\[ \frac{d}{dx} [f(u(x))] = \frac{df}{du}\frac{du}{dx} \]

If we ignore the fact that $\frac{d}{dx}$ is really an operator, and treat it like a fraction, we can multiply the equation by $dx$, giving

\[ d(f(u(x)) = \frac{df}{du} du \]

The above notation of $d$ expression is referred to as a differential. It is interpreted as an infinitely small change to the variable or expression to which it is applied.

Standard Derivatives

Here are the derivatives for a few common functions, expressed in terms of differentials.

\[ d(k) = 0 \] \[ d(u^k) = ku^{k-1}du \] \[ d(e^u) = e^u du \] \[ d(a^u) = (\log a) a^u du \] \[ d(\log u) = \frac{1}{u} du \] \[ d(log_a u) = \frac{1}{u\log a} du \] \[ d(\sin u) = \cos u du \] \[ d(\cos u) = - \sin u du \] \[ d(\tan u) = \sec^2u du \] \[ d(\cot u) = -\csc^2 u du \] \[ d(\sec u) = \sec u \ tan u du \] \[ d(\csc u) = -\csc u \cot u du \] \[ d(\arcsin u) = \frac{du}{\sqrt{1 - u^2}} \] \[ d(\arctan u) = \frac{du}{1 + u^2} \]

Wednesday, June 19, 2013

MathJax Test

This is a simple post to test that MathJax is working. MathJax allows you to embed Latex markup in an HTML page.

MathJax Test


Maths between dollars is inline: $\sum_{k=1}^n k = \frac{n(n+1)}{2}$.

Maths between slash-square-brackets is display: \[\sum_{k=1}^n k = \frac{n(n+1)}{2}\]

Saturday, June 8, 2013

Iterating Arrays in Objective-C

Objective-C provides several mechanisms for iterating through an array. One can

  1. Iterate the array by index
  2. Use an iterator to walk the array
  3. Use the for in syntax

The dummy program below illustrates these methods.

If you are working from the command-line instead of from Xcode, the compilation line is

gcc -framework Foundation array.m -o array

array.m


#include <stdlib.h>

#import <Foundation/Foundation.h>

static void printArray1(NSArray *array)
{
    size_t i = 0;
    size_t length = [array count];
    for (i = 0; i < length; i++) {
        NSLog(@"%@", [array objectAtIndex: i]);
    }
}

static void printArray2(NSArray *array)
{
    NSEnumerator *enumerator = [array objectEnumerator];
    id object;
    while ((object = [enumerator nextObject]) != nil) {
        NSLog(@"%@", object);
    }
}

static void printArray3(NSArray *array)
{
    for (id object in array) {
        NSLog(@"%@", object);
    }
}

int main(int argc, const char *argv[])
{
    int i;
    NSMutableArray *numbers;
    NSArray *sorted;
    numbers = [[NSMutableArray alloc] init];

    for (i = 1; i < argc; i++) {
        [numbers addObject:[NSNumber numberWithInt:atoi(argv[i])]];
    }

    NSLog(@"----------PRINT1----------------");
    printArray1(numbers);
    NSLog(@"----------PRINT2----------------");
    printArray2(numbers);
    NSLog(@"----------PRINT3----------------");
    printArray3(numbers);
    return 0;
}

Saturday, June 1, 2013

Using Bash and Awk to Print Long Lines

Bash and AWK are great tools for writing small programs. In this blog, we use AWK in a Bash script to print long lines in a file.

longlines.sh


#!/bin/bash

usage() {
    cat <<EOF

usage: $(basename $0) [-m MAX] [-n] FILEs...

Prints the lines in FILEs that have a length greater than MAX.
By default, MAX is 80.  If -n is given, the line number is also
printed.

EOF
}

max=80
printlines=0
while getopts m:n flag
do
    case $flag in
        m)
            max=$OPTARG
            ;;
        n)
            printlines=1
            ;;
        \?)
            usage
            exit 1
            ;;
        :)
            echo "option -$OPTARG requires an argument"
            usage
            exit 1
            ;;
    esac
done

shift $(( OPTIND - 1));

if [[ $# -lt 1 ]]
then
    usage
    exit 1
fi

awk -v max=$max -v printlines=$printlines \
    'length($0) > max { 
        if (printlines)
            printf("%6d: ", FNR)
        print $0 
    }' $*

Notice how the -v option to awk allows us to set variables in the AWK script from values in the Bash portion of the script.

The following example prints words in the American English dictionary that have more than 21 characters.

longlines.sh example


$ ./longlines.sh -m 21 /usr/share/dict/american-english 
Andrianampoinimerina's
counterrevolutionaries
counterrevolutionary's
electroencephalogram's
electroencephalograph's
electroencephalographs

An alternative way to write the awk portion of the script is

awk \
    'length($0) > max { 
        if (printlines)
            printf("%6d: ", FNR)
        print $0 
    }' max=$max printlines=$printlines $*

The use of -v makes the variables available to the entire script, including the special rule BEGIN; specifing the values as max=$max makes the variables available to all rules, excluding the special rule BEGIN.