Question

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section \(1.1 .7\) and the fixed-point procedure of section \(1.3 .3\) in terms of iterative-improve.

Short answer

Use `iterative-improve` to build both `sqrt` and `fixed-point` by supplying specific `good-enough?` and `improve` functions.

Step-by-step solution

Understand the Problem

Read the problem statement carefully. We need to create a procedure, `iterative-improve`, that takes two functions: one for checking if a guess is good enough and another to improve the guess. This should return a function that repeatedly improves a guess until it's good enough.

Define the Iterative-Improve Procedure

Design a function `iterative-improve` that accepts two parameters: `good-enough?` and `improve`. It should return another function that takes an initial guess and uses a loop to repeatedly apply `improve` until `good-enough?` returns true.

Specify the Good-Enough Function for sqrt

For the square root function, define `good-enough?` as a procedure that checks if the square of the guess is close enough to the number being square-rooted, using a small tolerance for precision.

Specify the Improve Function for sqrt

Define the `improve` function for the square root to be \( improve = \frac{guess + \frac{n}{guess}}{2} \). This is the average of the guess and the quotient of the number and the guess.

Implement sqrt Using Iterative-Improve

Use `iterative-improve` to create the `sqrt` function by passing it the appropriate `good-enough?` and `improve` functions. Provide an initial guess, such as 1, and call the returned function from `iterative-improve`.

Specify the Good-Enough and Improve Functions for Fixed-Point

For the fixed-point computation, `good-enough?` checks if the new guess is sufficiently close to the previous guess. The `improve` function is simply applying the function whose fixed point is sought.

Implement Fixed-Point Using Iterative-Improve

Create the `fixed-point` function using `iterative-improve`. Pass the `good-enough?` and `improve` functions suitable for fixed-point calculations. Initialize with a reasonable guess.

Key concepts

Numerical Methods

Numerical methods are mathematical tools designed to solve problems that are too complex for analytical solutions. These methods are essential in engineering, physics, and computer science. One vital technique within numerical methods is "iterative improvement," which aims to refine guesses for unknown variables repeatedly until the solution is sufficiently accurate. For example, finding square roots or solving equations often involves iterative algorithms, as they use approximations refined through multiple iterations. The key advantage of iterative methods is their capability to handle complex equations where no simple formula exists.

To effectively apply iterative improvement in numerical methods:

• Always begin with a reasonable initial guess and select a fine-tuned method for verifying the accuracy of your solution.
• Define clear criteria for when an approximation is "good enough."
• Choose an algorithm that incrementally approaches the result, like the Newton-Raphson method for finding square roots.
• Continuously improve guesses by leveraging mathematical operations that progressively narrow down the possible range of solutions.

Algorithm Design

Algorithm design is the process of defining a step-by-step methodology to solve a problem. In the context of iterative improvement, algorithm design involves constructing functions that systematically test and improve guesses. The objective is for the algorithm to produce results that meet a predefined accuracy level.

Designing algorithms for iterative processes involves:

• Specifying precise conditions for evaluating whether a guess is accurate.
• Creating an improvement function that effectively narrows down the error margin with each iteration.
• Ensuring the algorithm terminates after achieving the desired precision, preventing unnecessary computations.
• Utilizing loops that apply these functions iteratively until the "good enough" condition is satisfied.

Through careful algorithm design, complex problems like square root approximation become manageable by breaking them into simpler, repeatable tasks.

Functional Programming

Functional programming is a paradigm that treats computations as the evaluation of mathematical functions. It is particularly useful in iterative improvement due to its emphasis on immutability and higher-order functions. In functional programming, functions can be passed as arguments, enabling a cleaner and more modular approach to creating iterative improvement algorithms.

When using functional programming for iterative methods:

• Focus on pure functions, which return results based only on their input parameters and without side effects.
• Utilize recursion or higher-order functions to implement the iterative process cleanly and effectively.
• Functional programming encourages breaking down tasks into smaller, reusable units, enhancing code clarity and reducing duplication.
• Take advantage of features like lambda expressions and closures to encapsulate and manage state during iterations.

By adopting functional programming, developers can write more robust and error-free iterative algorithms that can easily be maintained and extended.

Computational Thinking

Computational thinking is a problem-solving process that includes a range of skills and techniques. It is central to developing and understanding iterative improvement strategies. This method enables one to decompose complex problems, recognize patterns in data, abstract general principles, and develop step-by-step algorithms.

Key aspects of computational thinking in iterative improvement include:

• Decomposition, which involves breaking down problems into more manageable parts, making complex processes easier to comprehend and address.
• Pattern recognition, which helps identify similarities between different problems, facilitating the use of standardized methods like iterative improvement.
• Abstraction, which simplifies complicated systems by focusing on the most critical components, thus reducing the cognitive load required to understand and solve problems.
• Algorithmic thinking, which emphasizes the logical progression needed to transition from an initial guess to an optimal solution efficiently.

Computational thinking provides a roadmap that guides both the planning and implementation of iterative strategies, enabling more efficient problem-solving.